I can now add and remove tracks on an iPod with 3.x firmware.
New songs dont actually play yet, but they do show up correctly in the menus at least!
EDIT: (The next morning). Doh. I had a '\' instead of a '/' in one of the filename fields. I played the new track the whole way through, and it enjoyed it more than ever before lol!