Personally, I don't know why your trying to play 1080p video on a 720p device. In that sense, your creating unnecessary stress for the device which doesn't even support those formats. Plus, your wasting memory space.
Not trying to defend the Nexus's apparent shortcoming, but I've always gone under the assumption that if a video is not less than or equal to the device's native resolution, and isn't MP4, there is no guarantee it is going to work.
That's my philosophy, you may disagree, but I digress.
I personally would try converting it to 720p H.264 MP4 since its a tried and true format. I know its a bit inconvenient, but for a PC with a modern processor, this shouldn't take more than a half hour, maybe an hour, tops.