Check your work group name.. I had a problem with older (win98/ME, forget what it was, but it was *not* mshome) used a different name than XP used and couldn't see each other.
PS, which did you reinstall? XP or ME? XP (sp2) has a firewall, and I've seen conflicts between other software firwalls and xp's (shouldn't have two active at once).. If on the ME, then nevermind...