That didn't quite go as smoothly as expected!
There is an official ClockworkMod recovery ROM for the Nexus 4 and that's what I used on my Nexus 7, so I thought I'd go that route.
Oh god.
Once I flashed it on it started going into a boot loop. I couldn't access recovery via the boot loader (loop again) so had to do it via fastboot command. When CWM started, it was showing mount errors and nothing would work.
Tried starting phone normally, but it seemed to take forever on the "Google" screen before heading to the nexus one....and then it just seemed to get stuck there.
Bit of panic at this point.
In the end I downloaded the stock image from the developer site and reflashed everything and hey presto, the thing started up.
The odd thing is that it would appear that I accidentally flashed on the CWM recovery during my full restore (judging from the filenames), so I think I have CWM installed and the phone is starting normally.
For the moment I'm not going to risk it again, I'll wait a while until these issues with CWM have been ironed out, reading the thread over at xda I'm not the only one who ended up with a device in this state.
Still, bootloader is unlocked now.