Apparently this is a common problem with AT&T U-Verse and range extenders like the Netgear WNR2000RPT. I was able to resolve the problem by following the advice found on this blog: http://stack247.wordpress.com/2011/04/12/using-wireless-extender-netgear-wifi-range-extender-wn2000rpt-on-att-u-verse-router-windows-and-macintosh/.
I would paste the relevant content here but my mobile device is not letting me access the editor here fully. I will try to quote the content here when I get back to my computer.
Interestingly enough for me the problem only affected Windows machines connecting via the range extender. Linux and iOS devices are not having any problems.
Anyway, by following the advice in that post I was able to get the Windows-based devices online. It is not an ideal solution but it at least gets you online. If I find a better solution I will update this answer.