Time Warner did this a while ago as well in my area, and did something to their DNS servers to break Back to my Mac. My fix was to switch over to OpenDNS, and also disable all their "helpful" pages.

The worst part for me is that the browser wouldn't know I typoed a domain, and remember it, causing it to suggest the typo version in the future as an autocomplete suggestion.