The Problem
I don't believe your biggest issue is "should the selected be on the right or left"--I think what hurts it the most is the fact that those arrows communicate nothing.
In my experience, using the arrows you have in your lists requires more processing because they point from left-to-right or right-to-left, but they're positioned vertically. It wouldn't make sense to position them next to each other (as they describe an action not between each other, but between the two lists). Additionally, they don't communicate which side the "selected" items are on, so the user has to look for headers or other context clues to find that out.
The Solution
I find that Microsoft has solved this quite well.

In the screenshot, Microsoft changed the buttons to "Add >>" and "Remove". This gives much more immediate affordance as to which button does what you want, and where the "selected" items are.