A decent middleware would be a good start. Luckily all the consoles are PowerPC-variants, but most PCs and (increasingly Macs) are x86-based. From looking at some of the Mac ports of popular PC games, we know that networking is impossible at times because of how the x86 and PPC chips handle endian code differently, back when it was just PPC Macs.
Valve said they had a version of Team Fortress 2 that could network the PC, PS3, and Xbox versions, but it was too buggy and a hassle for a real consumer release.
Then there's the problems of the servers themselves as GFLPraxis has pointed out.
But yeah, it's shame we have so many awesome games that are available for all platforms, but incompatible when it comes to online play (Guitar Hero III, Call of Duty 4, and The Orange Box being good examples). It sucks the consumer has to choose which platform to buy their game for (assuming they have more than one console and/or a PC) and hope everybody is playing it on the same platform.