OK, as soon as I posted it struck me that there must be a field that holds the FB ID and indeed there is. JUpgrade cunningly decided to leave that field out, as well as all of the Avatar image names and a few other columns in _comprofiler.
Having checked that the columns are the same a quick SQL import export has sorted that out. I am now able to login using FB Connect
Just need to find and upload those avatar images now and we should be back in business.
Hope this little rant of mine will help someone in the future!