This is a known issue. You're not limited by the number of downloads; you're limited to a total number of *devices* that you can download to. The publisher actually has the option of spcifying the limit, but the default is 6 devices. The only real problem is if have more 6 Kindle devices. When you deregister the old one your licenses are not automatically "freed".
However, it's not true that you're required the repurchase the book. Amazon will individually free up licenses for you if you call and ask. Also, they also have the option of refunding your money and letting you buy the book again.