Cisco Linksys Router, specifically the WRT-160N model. It appears there is a bug in this routers recursive DNS implementation in firmware and Linksys refused to acknowledge this.
Solution (this appears to fix it):
Configure your local computer to use DNS servers INSTEAD of getting them through DHCP (when the router gives your computer networking information).
Good luck! Let me know in the comments if you are having this problem with other routers.
