But my Lubuntu machine still doesn't show up under "Network" on the Windows machines.
 Run the following command in lubuntu and count the number of characters:
If it's 16 characters or more in length then your machine is invisible to the rest of the network.
 Change the order of how host names are resolved to ip addresses:
To do both:
Edit smb.conf as root ( I'm using gedit here because I don't know the default editor in Lubuntu ):
Then add the following line to the [global] section of smb.conf - right under the workgroup line to fix the hostname problem if there is one:
gksu gedit /etc/samba/smb.conf
something must be 15 characters or less in length
netbios name = something
Still in gedit add another line under that one:
Save smb.conf and then restart samba services:
name resolve order = bcast host lmhosts wins
Note: Every time you restart samba services the network has a fit so wait a few minutes and see how far this advice got you.
sudo service smbd restart
sudo service nmbd restart