Well, here are screen shots of two gradients:
don't think more grey is what's called for!
the green's a bit more successful - but would need some tweaking... (points taken about introducing more colour)
I kinda like the idea of defining the navigation area a bit more (but without getting too boxy)
I've tried a horizontal gradient coming in from the right: interfered with the content too much
krycek: I particularly like the sound of your arguments - I guess I know how I'm spending my Saturday night...