NOTE 10.1 (2012) HDMI not displaying correctly
I have fiddled around and found that altering the decode mode from HW to SW or System player in BSPlayer fixes the issue! This also works for MXPlayer too.

This results in the correct video ratio although it is not full width on a 1080p tv (just like my desktop) it is at least not stretched. I still don't get why Google Play Movies can play its native videos full width on my tv.