Assume I'm getting a new router. I've never heard of any problems like this, but is there reason to fear some routers might not work well with Ubuntu? If so, which types?
Every router in existence should work with Ubuntu. Routers communicate with your computer using plain TCP/IP, the operating-system-agnostic backbone of the internet. Without getting too technical, any operating system that speaks TCP/IP (which Ubuntu does) will work with any router.
If you're setting up a network with multiple routers, stick with one vendor (eg Linksys, Belkin). There can be interoperability issues there, but that also applies for Windows and Mac.