I've never had any problems with software update until I reformatted my hard drive, and did a complete clean install. I installed from my system disk (8.6), upgraded to 9.0, and then upgraded to 9.1 one after another. I then copied a few preferences, such as TCP/IP, Remote Access, Modem, and Internet, from my backup, and any other updater programs that I happened to save.
My connection to the internet works well (ie remote access, web browser, email, etc.), but when I try to use Software Update, it starts up and starts the looking for update proccess, and then after about a minute or two, it tells me that it can't find a connection to the internet, and to reconfigure my connection. I updated to the new version of software update, but I still had no luck. I've tried everything from trashing all internet preferences, and starting from scratch, to trashing software update prefrences, to adding software update preferences from backup....Nothing Works, and I know that I don't have every update that's out there!!!!