Can't Add Applications

[Staar]

So I installed Ubuntu 6.06 (Desktop Version).  
When I attempt to add any applications using Add/Remove Applications I receive an error: "Could not add application to the application database".  I was connected to the internet via a really slow dialup connection (12kbps).  Could that be what the problem was?

I dont know if it's significant but when I first booted from the cd I was unable to select the first option - Start Ubuntu.  When I did, the pc would reboot and the same screen would appear.  When I selected 'Start Ubuntu in safe graphics mode' it was able to continue.