apt-get update doesn't do much.
It just updates your current package information database.
Since you have an old database, either a) privoxy isn't in it or b) the dependencies are all old and non-existent.
Until you do 'apt-get update' nothing with apt-get will work, and on a Debian box that's pretty useless. :-)
Regards,
-scott anderson
"Welcome to Rivendell, Mr. Anderson..."