I dunno, but it's the most plausible explanation I've seen thus far. Is Ubuntu 12.04 running Samba 4, because that's supposed to be more compatible with latest windows (or maybe ubuntu backported the patch for it, which they've been known to do, unlike microsoft)?
http://support.microsoft.com/kb/2793313
Edit: Must be true because I applied the patch to Windows 7 registry, rebooted and Windows 7 can now see all the shares on W2k and connect straight up with no password hassles.
EDITED: 24 Feb 2013 13:22 by DSMITHHFX