So you are absolutely sure it's not this:
http://www.e90post.com/forums/showth...=shifter+wires
On mine, we had to remove a bit of trim on the shifter to access the wires which had been damaged. Look at the photos of the damage at the end of the thread, you'll see why it wasn't working correctly.
The problem you described sounds exactly like symptoms mine had, I am very surprised if all of your wires are fine.