Update - I think we have solved it.

I installed a tool called DelegConfig (http://www.iis.net/downloads/default.aspx?tabid=34&g=6&i=1434)

This flagged up that one of the SPNs was incorrect - I had included the port number....