Is it possible that you have the little check box that reads "Share the following playlists" checked, but no playlists are then checked. That is my first theory at least.
Also, I have no idea if this is valid or not, but are the two iTunes installed with the same version? Do you have differing OSes? Is it possible that you have a firewall on one machine but not the other?