I would say that possibly you have a bad or damaged capacitor, and that it should definitely be replaced...
As others have mentioned, the only real way to accurately measure the cap would be to desolder it and test it alone. Your handheld run-of-the-mill RadioShack DMM probably won't be accurate enough to read out the values, I would say use an RLC meter (one of the bench-type ones) if you can. They will be more accurate in the picofarad (or maybe even femtofarad) range.
Also, check your circuit - in the photo you posted I see the cap in question soldered in series with what looks like another cap, hence the high capacitance value. I would check the other cap is soldered where it needs to be, just in case that you actually have placed it wrong.
Another thing I noticed - you said it worked on the breadboard. Did you use this exact same cap on the breadboard? If so, try to figure out what possibly could have gone between the breadboard and the perfboard, including the demon we know as ESR.
I would also check the reputability of the manufacturer of the cap in question. If it's a crap manufacturer who make some crap quality caps, then that could be your issue, is that you have a crappy quality cap. KEMET has some good ceramics and tantalums, but if you got yours from a brand that makes bad caps and is known for it then I would say try a different brand and see if you get the same result.
Edit: Check the BadCaps forum, they might be able to help you more than I can: http://www.badcaps.net/forum/index.php