I have enabled the Rotates with my current direction setting, and pulled up driving directions, but Maps never rotates with my orientation.
How does this feature work?
Looks like it only works when you get directions. So in the bottom you can see the directions and the map will rotate.
You can see in below picture the map was turned.
You can see the same location with Bing Maps here;