I'm not a Ubuntu user (gentoo instead), but I came across this thread while researching this same problem that you all have experienced. In hindsight it seems obvious, but instead of wiping the BIOS memory by unscrewing everything and unplugging the battery - just reset the BIOS back to its default settings.
Reboot -> F2 -> F9 (load default BIOS settings) -> F10 (save & exit)
Worked for me.
Thanks to kquigley for pointing this out (see http://forum.meego.com/showthread.php?t=2011 )