There has to be some difference, It may be as simple that you are cloning into a lower layer and can not see the clone or you trying to clone into a smart object layer. That can not be done.
Showing a screen capture of your problem would be helpful. As would a sample image file
There are several reasons why you would get this error. The first, would be trying to clone on a "background" layer or a layer that is locked. If you see a lock there, you can't clone. Also, pay attention to the "Sample:" drop down menu at the top, where the clone stamp options reside.
If it is set to "Current Layer" and you have created a blank layer above the image (as you never want to work destructively and clone on an image directly), and there is nothing on said layer, you will also get an error.
Another reason to get this error is if you are trying to clone out side a selection area. Did you make a selection somewhere and are trying to source outside that area? Ding, you'll get an error. Also, perhaps you hid your selection (hitting command + H). Hit command + D to deselect all or hit command + H again to reveal the selection and if all layers are unlocked and you should be able to clone. Those are the ones I can think of off the top of my head. You also can't clone on the obvious adjustment layers or vector layers. If you could do a screenshot with an image (including the layer's palette) where this is working vs one that is not, I can help you get this sorted in no time.
This sort of thing is probably just something minor (like what I mentioned above) you are overlooking. Not sure where you are, but at the end of a long day of retouching (its nearly evening here), I know sometimes silly things can get overlooked. Cheers!