Hey, I also had this problem (on Shield Tablet with Android 5.1.1) and I've already provided the solution, but somehow my message has not appeared here - I don't know why and I also don't know why it has been invisible for dislekcia here... there has been some message about the moderation because it included the link with the detailed explanation of the problem, so maybe that was it?
So, another try, this time without the link:
First, the SOLUTION (that worked for me): simply unmount the microSD card (you don't even need to eject it) and the installation should work this time.
Then, the explanation: stupid Android bug is preventing the installation (and also moving) of the app to the external SD card if the card is too slow (it is related to some constant timer that times out and breaks the whole process in the middle), regardless of the amount of the free space available. Unmounting the card forces the app to be installed to the main memory: there are no timers, so it works.