I suggest vertical, on the right side.

Explanation: You have navigation and scrollbar close together, there is minimum of mouse movement involved when navigating through site/content.

Unfortunately, there is no way to change the side of the scrollbar. If a left-handed person viewed the site, there could be a style switcher to move it all to the other side. I wonder why this feature has been overlooked ...

Apart from that, this is a difficult question, since AFAIK the majority of users expect navigation bars on the left side. So I think there might be a psychological barrier for right-side nav bars. If you build a geek site like alistapart.com, no problem. But for real business? I would stick to left side.

Alex