I haven't used Privoxy much, but I would assume that there's an option to change which addresses/ifaces it listens on, as with many other services. Did you double-check that it's not set only to listen on localhost? My apologies if you've already thought of this, but it was the first thing that came to mind after reading the symptoms.