I can strongly recommend the Crumpler range of laptop bags - they have bags for pretty much every need (other than hardsided leather or metal!).
All Crumpler bags are made from heavy-duty nylon fabric, strongly stitched, very high quality finish. Their laptop compartments are well padded, and their carrying straps are seatbelt webbing. They use velcro and black nylon fasteners.
They have bags designed to hold nothing but the laptop (to put inside a briefcase, for example), bags designed to hold a day's worth of stuff (charger, papers, etc), and bags designed for travelling (back-pack for laptop + heaps of stuff). They even have specialty bags for photo-journalists - backpack to hold laptop + camera/lenses/flash + stuff.
They also have a range of add-ons - things like a little bag for your cell-phone that attaches to the strap of your laptop bag.
They come in a wide variety of colours, too - from bright and cheerful through to sober and business like - such a refreshing change from a line of all-black laptop bags
I have no financial interest in Crumpler, but I have several of their bags (two laptop bags, two camera bags, and a couple of general purpose bags). They are not expensive for the quality (read, typical Crumpler bag might be US$100).
Oh, and one of the coolest things is that their laptop bags and camera bags do NOT scream out "I am full of expensive stuff - STEAL ME"!
You can find the main website at: http://www.crumpler.com.au
but be warned - this is a STRANGE web site - it takes a bit of getting used to!