Have you checked all the settings? I noticed some software will do stuff like turn firewall on or make other changes without asking. Nothing else is coming to mind. Hopefully someone more network savvy will chime in.
Don't ask me why but one thing I found useful when trying to get XP and Vista/Windows 7 to network with no passwords was to not share any folders at first. Just use the default shared folders, All Users and Public. For some bizarre reason it seemed like once I got those going, then I could enable sharing on a regular folder. Go figure!

I'm just grasping at straws at this point.