Trying Fedora won't solve AJ's problem. His problem is probably that his apt isn't configured properly. This happens to everyone every once in awhile, it has happened to me too. So even if he installs Fedora and uses synaptic or smart, it's probably going to get fucked up one day, like when a certain version of apt is incompatible with a certain repository that the distro requires, or something like that (I think my problem occurred during the FC3-FC4 upgrade). It would be so much better for him to figure out how to solve it. Tossing a distro if it has a minor problem like this is like buying a new car after your friend vomits in your front seat.
Although I am not a Ubuntu guru (I'm barely a Ubuntu user), I suspect that AJ's apt problems are being sugar-coated by the gui - it doesn't give him any useful information, just a failure notice. That's one of the drawbacks of trying to hide everything from the user. If you want things to work, you have to have useful feedback and you might even have to get your hands dirty.