I know this sounds like a cop out... but..........
I had terrible problems of exactly the sort you are having.
Days were spent trying to find a fix.
In the end, I was pointed to lesser known option by YannBuntu:
Re-install while keeping ones data and settings.
It's an honest 2hours work, but most of that is spent doing something else.
If you can't find a fix, you should definitely try it cos it's tried and tested.
Consider using a 12.04 disk for the re-install, until the probs are sorted in later versions.
The link is in my signature.
The guide is my step by step for noobs, but it contains the links to all the key resources you might need.
It's a decent last resort (or first resort if your stuck for time).
Bookmarks