You don't have to go back to "stock" before upgrading the firmware. If you insist... uninstall the ss hack and the jailbreak with the uninstall programs that come with them.
Do a factory reset.
Update to latest firmware.
Install jailbreak/hacks.
I believe 2.5.8 is the latest for the second generation Kindle. That's not going to give you any new whistles and bells that 2.5.6 doesn't have. I'm still on 2.5.6 with all of the hacks installed successfully.
EDIT: ...and yes, don't post your entire serial number on public forums.