Have you tried something like Spiceworks? You tell it the network to scan and it will identify nearly any device on the network. Feed it SNMP and login information and it will pull specific information from those devices to help map the network. They have a network mapping utility that is still in beta, but it seems to work decently well.
Visio has a plugin called LanSurveyor which will scout your network, identify nodes, and plot them out. It is put out by Solar Winds, and has a free trial. Their express version was available free through a promo which I don't know is still active or not - here's the link for that:
I did not see these mentioned in this thread, so I thought I would list some of the other programs which also do this sort of thing. These are all high end programs, so don't expect to find free versions however you might get the benefit of using a trial copy just to see if you like it.
HP OpenView - Excellent tool and one of the industry leaders
CA Unicenter - Extremely high end and powerful but is difficult to set up.
I find that WhatsUp Gold to be an ideal program for this. All you do is point it at your network segment and it will scan and identify every device which responds back. Their website is http://ipswitch.com . There are trial versions of this software out there to be had and I am sure the company will give you a trial copy too.
This is perhaps the simplest and most intuitive tool of this type that I have used to date. It also has a web server feature which will allow you to move around the network if needed.
I find the graphics of this program certainly nice enough for a quick and dirty map of the local network. You'll find it worthy as well!