All right, I'm back and I'll try to answer each of your suggestions.

Both computers are running Windows XP Home Edition, sp2.
The run box doesn't work whether I use \\Other Computer's Name or \\Actual IP
Also I can't browse one computer from the other, but see my final comment at the bottom.
I don't think I've been messing with my services, at least not that I remember. It simply was working one day but wasn't the next day. Maybe my daughter did something but she says she hasn't.
The username and password happen to be the same in both computers but this never caused any trouble before.
As for updates, I couldn't say, though one of those minor Windows updates or occasional patches is quite likely.

What I did first thing when I got back was check the computers' names and work groups. Then I thought I'd found it because the work groups were different. I then changed this in one of the computers and re-booted, but still the problem remained: if I tried to browse the local network, the other computer just didn't show up.

I also tried to reset the router to no avail.

And the final comment: the problem seems to be unidirectional. From one computer I can see the other but not the other way round!