I am putting up some shelving today. Unfortunately, the wall anchors don't seem to be taking. I used some plastic ones which didn't work as I was able to pull them out of the wall about half an inch. I purchased some larger (http://www.homedepot.com/p/Cobra-Anchors-1-4-in-x-3-in-Zinc-Plated-Driller-Toggles-4-Pack-367R/202531181) toggle bolts and those aren't working either. Short of replacing the drywall at this point, I'm not sure what I can do to make this work. Any suggestions?
It sounds like you want to keep using the existing holes, which by now are quite stripped and loose.
As mentioned in the comments, for a shelf you almost certainly want to fasten it to studs. However it is possible (though not advisable) to have a shallow, light shelf supported by drywall.
So if you are unwilling to mount to studs, consider using heavier-duty Toggle bolts as they stronger are not affected by a warn-out drywall hole. The bolts you linked are one of the weaker kinds and seem to rely on a snug fit. There are even more advanced versions, like the Snaptoggle that boast impressive strength, but most people remain skeptical about those claims.
No matter what fastener you are using, you are ultimately limited by the strength of your drywall. Thicker drywall is stronger, but all drywall will age and weaken over time. A shelf that feels sturdy to begin with may weigh on the drywall and cause it to sag over 10 - 20 years. Environmental factors such as the amount of vibration (from minor Earthquakes or from heavy truck or train traffic near by) will affect the rate of deterioration.