This is really strange because things look ok.
A couple more questions...
Can the both machines still see/access shares on the other machine? You said earlier that print and file sharing was working but has that changed?
Check the workgroup name on both computers? If you took the defaults and ran the Wizard on both machines I think it would be MSHOME if they are different make them both the same. Doesn't matter what just make them identical.
Are both machines XP Home or XP Pro? It shouldn't matter but ...
Have you installed all/some of the updates from MS for XP? The most critical, for this issue, is the first one that was released right after XP was released in October. If not, get it and install it. The later updates are security related and important but should not be affecting us here, I hope!
I'm getting stumped here, grasping at straws. As a last resort, if you haven't already tried it, delete all your connections (Lan and modem) on both machines, reboot, create the modem connection, (the Lan connection should be discovered and established on boot) and rerun the Network Setup wizard on both machines. Maybe all the fiddling has messed things up.
Double check all the Causes/Solutions I posted earlier.
Sorry about this, I hesitate to quote our last President but, "I feel your Pain". Keep trying!

This 'feature' is working on a whole lot of machines and it should work on yours! I'll keep looking for an answer.
The two rules for success are:
1. Never tell them everything you know.