We are having the same issue with API failures at buzzdeck.com, using the Instagram API to collect metrics on user accounts. We're requesting users recent media by page (getting approx 33 items per response even though you can request up to 250), and some page requests work, and some fail - usually the same ones that are failing.
In concordance with what you have seen the issue appears to affect some IP addresses but not others, since some of our servers have been unaffected. We have verified that we're not coming close to API rate limits, and that the Instagram Client app used to make the request makes no difference. We have raised the issue twice with developer support but have had no response from Instagram. Very frustrating!
[EDIT - 15/04/14] Issues have now been resolved by Instagram support, if you're still having trouble it's worth contacting them with the specific IP addresses from which you're making requests