So after a few more tries I found that the stock recovery.img started working after I flashed TWRP and then flashed the stock one, no idea why this would fix it. The real problem with the OTA update was that my Super-SU install from before had modified the /system/bin/install-recovery.sh file and the update process would fail when it checked the validity of this file. So I flashed the 5.1.0 system.img and was then able to get the 5.1.1 update to install. But the regular update procedure wouldn't work, I had to use adb sideload update.zip whilst in recovery mode.