I ran into a similar problem when I installed a new HDD and updated my PowerBook to OS X 10.4. I had to re-authorize it for iTunes, and in effect lost one authorization.

Once you have used all your authorizations, a button labeled "deauthorize all" will come up in your account information screen. This will deauthorize all computers associated with your iTunes account, including those you no longer have access to, or those authorizations that were lost due to servicing or an upgrade. You can then authorize up to five computers again. Apple will let you do this only once a year, however.

Somewhere on the iTunes web site it tells you to make sure to deauthorize your computer before bringing it in for service. Unfortunately this is not intuitively obvious until after the fact.

Hope this helps.