Right the category from which they originate, will still show them in the original category on the index. If you go into the category, they have been successfully moved.
The problem is, I have to go into the database and update those two fields manually. I'm not quite sure why...
http://notbusy.com/c/db.png < have to update that when using bulk actions