Just found this info in the Backup dashboard widget:
Starting manual backup
Backing up to: /Volumes/tm2/Backups.backupdb
Inheritance scan required for /, associated with previous UUID: [deleted]
Event store UUIDs don't match for volume: exxi_hd
Deep event scan at path:/ reason:must scan subdirs|new event db|
First backup after disk inheritance for / - complete scan required
Found 839161 files (154.88 GB) needing backup
188.83 GB required (including padding), 145.37 GB available
Deleted backup /Volumes/tm2/Backups.backupdb/exxi/2012-03-04-160328 containing 2.25 GB; 147.63 GB now available, 188.83 GB required
Deleted backup /Volumes/tm2/Backups.backupdb/exxi/2013-02-05-181442.inProgress/57E7F008-929C-4 DF8-B062-F034FEE7A606 containing 4 KB; 147.63 GB now available, 188.83 GB required
Deleted backup /Volumes/tm2/Backups.backupdb/exxi/2013-01-07-112745 containing 130.8 MB; 147.76 GB now available, 188.83 GB required
Removed 3 expired backups so far, more space is needed - deleting oldest backups to make room
Deleted backup /Volumes/tm2/Backups.backupdb/exxi/2012-03-11-191620 containing 2.08 GB; 149.86 GB now available, 188.83 GB required
Removed 4 expired backups so far, more space is needed - deleting oldest backups to make room
Backup deletion was canceled by user
Deleted 4 backups containing 4.46 GB total; 149.86 GB now available, 188.83 GB required
Backup date range was shortened: oldest backup is now Mar 31, 2012
As you can see from the log above, time machine had attempted to make a full backup. In the end, I decided to let it run and I'm now left with backups dating back to JUN 2012.
However, this morning I discovered another issue and I think this might explain why it decided to make a full backup.
I scrolled back through my recent backups in time machine and as I went backups from before the switch to the new iMac I found they were all empty. Looking at the time macine volume directly I can still see the files however, I have no permission to read them. All files are owned by "temp" which is a temporary user I created for restoring the backups. I did this because when I first setup the new iMac I used my real account details and then found that I couldn't restore the backups as it was complaining that the user existed.
So I think the real problem is that I setup the temp user as the first and only account when I reinstalled OS X and this meant temp got the UID 501; therefore, all old backups which were created under my real account which also had UID 501 were linked to the temp user. When I created my real account account I was assigned ID 502. Hence the need to create a new full backup.
Not sure what to do now...