So you can surf web pages and all that? (if not, that would first need to be possible)
Try running apt from command-line to see the "real" error messages:
Code:
sudo apt-get update
That ought to update the list of available packages, and if it doesn't work out, tell what the problem is. If it can't reach the servers you might want to edit the sources list file to use some other mirror (that is closer to you).
To install packages via command line, if you ever need (Add/Remove does this I guess, it just doesn't show it to you)
Code:
sudo apt-get install packagename
