I had the same problem, but found the answer somewhere on these boards (sorry, can't find the post now).
If the files were originally on the Kindle under their old title, you need to not only delete them from the Kindle but restart it (Menu > Settings > Menu > Restart on mine), then send the new versions from Calibre (Send to Device). Apparently the Kindle can be a bit reluctant to let go of stored metadata.
|