There isn't, by any chance, a shortcut to the contacts app on a desktop other than the one you're trying to add it to?

If so, delete it from that desktop. It will then show up as available to be added to the desktop you want to add it to.

I've got shortcuts to both Contacts and Conversations on my initial desktop - can no longer remember when I put them there.