I did some more digging and here are the links to the files directly from Amazon. I've had that archive around for a while for may have had a corrupted file though I'm kinda doubtful about that.
Your serial number starts with B003 download this file:
Update_kindle_2.5.8_B003.bin.
After your device has fully updated, download and install the
Kindle Services Update.
Note: If you have a software version before 2.3, download and install
Software Update 2.3 first, and then complete the steps above.