One item in the rebuilding phase I did forget was to deauthorise my computer from iTunes. Soon after clearing out the discs I realised that I didn't do this. I thought to myself that I've not added or removed anything so if it's generating some sort of hash based on the hardware to uniquely identify my machine I should be OK.
I just linked up my iPod and iTunes nicely told me that by BidiPod is linked to another music library! So I've now lost one "licence", possibly irrecoverable, due to the fact. IMHO, this should be a bug, I'll log it as such with Apple and hopefully my lost licence could be regranted.