There are different kinds of solder, very often, PCB's that have been manufactured use a very different solder than what you can get at radio shack, and the two don't work well together (ie they don't stick).
I've found the best solution to that is to buy a tub of Solder flux (radio shack DOES carry that).
Clean the pad, dab on a good bit of flux, make sure the iron is hot, touch the iron to the pad with the flux, and touch the solder to the iron and let it flow to the pad.
I've had probs like this, esp when trying to solder to the end contacts of batteries (ie when replacing batteries in shavers or cordless phones with home built AA packs).
Even if your solder says that it is "solder and flux" together, I've found it's usually not enough flux to let the solder really stick.