Do you have the 2 machines set up as a workgroup? If so, make sure the workgroup name is the same for both machines.
It's easier to use a hub or switch with normal ethernet cables, than to use cross-over cables to connect the 2 computers directly. This way, you can just plug in an additional computer into the hub or switch if need be w/o interrupting the other 2 units.