OK, it wasn't a fuse or relay - definitely the immobiliser. Luckily a mate put me in touch with an auto electrician who removed the system for £60 (inc call out). Not too bad overall, but an expensive battery!
Still, a lesson learned and all that.... Hopefully someone will read this and avoid the same mistake. In future i'll always hook up a temporary power supply when changing a battery.
Thanks to all who offered advice.