I'll try keep this as simple as possible. Basically we have a two-machine LAN (all fully working, both show up in the network browser, no internet connection sharing is enabled, file sharing fully working, pingable etc with static IP addresses), and when we start one machine running a LAN game (e.g. Battlefield 1942), the other machine can see the game and connect to it with no problems... but the minute we enable the internet connection (crappy 3G mobile broadband), the LAN games no longer show up. It doesn't appear to be the firewall, as even with it entirely disabled the exact same thing happens. Internet enabled, no LAN games can detect each other. Disable the internet, LAN games show up.
I had heard of this showing up in earlier builds of Windows 7, however both of these are the final Ultimate and fully activated so it's kind of a serious problem.