The rat shack (and indeed, most low-end) boards are made on a paper-phenolic base, which is cheap and easy. Most low-end consumer goods are made the same way. These are generally good for "one-time" projects- reworking is NOT recommended, as you've noticed, because the copper pads don't tend to adhere too well to the board. Plus, overheating that phenolic material releases some pretty gross substances into the air. I've also noticed that many of these boards come "pre-oxidized", meaning they aren't plated and the copper surface is...dodgy...for soldering to. A quick burnish with a piece of steel wool or an SOS pad will do WONDERS for their solderability. You can also use rosin, but I never have and I haven't really seen much of advantage when I have.
High-end proto boards, like the Sparkfun ones (I'd imagine- I'm too lazy to check 'em out) are made on a fiberglass substrate (most commonly FR4). These have their advantages and disadvantages: they are much more durable, usually have pads on both sides, and tend to be plated so they stay solderable longer. They also tend to be more expensive and sometimes have little fuzzy fiberglass edges that make me want to puke when they poke my fingers.
My preferred method is to buy the cheap ones and be very, VERY careful with my soldering. AEI (at the intersection of 55 and 100) sells some that look suspiciously like a solderless breadboard. These are REALLY nice (despite being phenolic-based) because you can breadboard up a circuit, work out the kinks, then build up your final copy on the protoboard.
Your rework method might also be a problem. Do you use a solder sucker, solder wick, or both? I don't own a sucker, but I use one at work sometimes. I haven't found enough of a need for it to buy one, but they tend to be cheap and worth the price if you rework a lot. My preferred method is to suck off the gross excess with one or two pulls from the sucker, then draw out the rest with solder wick. You also want to be sure your iron isn't too hot. If you're doing a lot of soldering, you should consider a high-end solder station with variable temp and feedback. I got a nice Weller unit for around $100 a few years back. Note that the rheostat models that you plug a regular corded soldering iron into are acceptable in a pinch, but since they lack the feedback, you are still kind of shooting in the dark.
You also want to make sure your tip is nicely tinned (it should look like a bright matte metal, rather than dull or rusty). You can keep it healthy longer by either wiping it on a damp sponge after every joint or by getting one of those copper coil poof things that you plunge it into a few times. The copper both traps excess solder and burnishes off any contaminants (which will be there, in spades, if you are using rosin core solder, which is to say, 99% of the solder on the market). If the solder sticks to your iron tip instead of to the workpiece, and you KNOW the workpiece is hot enough, it's time for a new tip!