I've had similar issues with Ubuntu upgrades in the past. I went to Debian (stable) instead, figuring the longer upgrade cycles would mean fewer problems. That was all well and good until I needed to enable backports to upgrade Firefox to >=3.5 for work. Now the package manager's broken due to some weird dependency issues.
I don't understand why there is no free software equivalent of Apple, selling (laptop) hardware and maintaining a GNU/Linux distro that's guaranteed to work on it. Surely there's a buck or two to made?