Have you tried to uninstall/reboot/install the Mac software? Usually that helped for 2.5 update. If it does not help you can always uninstall 3.0.1 and install 3.0 back.

BTW, what Mac OS X do you have: 10.5 or 10.6?

Edited: I've just though that server (not client) update might changed permissions in the Mac share, or something. It might also change default Firewall settings, etc. I read something about such cases before. So connect RDP and re-check everything on your server. (Reinstalling Mac client won't be harmful under any condition).

I just upgraded my MSS to the EX495 and upgraded my Mac client to 3.0.1. I did, ultimately have to do a full uninstall of the HP software from the disk image and then reinstall it to get Time Machine to work on the client. Even using App Zapper on the HP software did not get rid of it.

I would not recommend to use such things for the software like HP MSS Mac Software, because its (App Zapper) logic is very trivial, whereas HP's solution is very complicated including services, drivers, etc., which should be uninstalled properly, otherwise it might be harmful even for entire system.

Ah, I did not know that. I'm used to Apple applications being pretty straight forward and what you just elaborated on probably explains it.