I've done this many times in the past and it works, but for some reason
when I add formats to the settings of my media device (A Rockbox'd Ipod),
the settings don't stick. When I click OK then go back into the settings,
they're already reset (without the added formats). I've tried remounting,
readding the device, ensuring codec support, and even reinstalling Amarok.

Anyone have any ideas?

check for other threads on similar topics - one of them has the answer.