I wrote an article on this a while back - it's not a definitive answer but addresses the suggestion that right-hand navigation might be more efficient.
However, I have to say that 'people usually figure things out' is not good evidence in favour. You can do a number of things that people will figure out, but at some point the cognitive loading will just become too much and they will bail out.
The article is at http://www.syntagm.co.uk/design/articles/navright.htm (more along similar lines at http://www.syntagm.co.uk/design/articles.htm)
User Experience Strategist
US Toll Free 1-866-SYNTAGM
Syntagm is a limited company registered in England and Wales (1985).
Registered number: 1895345. Registered office: 10 Oxford Road, Abingdon OX14 2DS.
From: firstname.lastname@example.org [mailto:email@example.com] On Behalf Of Dave Tanchak
Sent: 17 July 2010 02:39
To: William Hudson
Subject: [IxDA] Right-hand navigation
We're working on a new site design and some initial user testing has shown that our local navigation is just as effective on the right side of the page as it is on the left...