Thanks for the feedback.
The behaviour only happens when there is an advanced option on the item like size or color for example. Products without this don't appear to have a problem.
For products with advanced options I can remove the product from any category and it doesn't appear in the new category. Once I add it back in it then shows in both the old and new cateogory. The product always remains in the old category. If you remove the product from all categories and then remove the category it deletes all the products that were included in the old category that came across from PS2 into PS3.
I'm not sure if I am on the same page with looking at which categories an item is attached to. Could I have a field missing? I can't see a field that has multiple categories listed in it.
In the ps3_productcategories table product ID 707 is attached to category ID 8 and 115 and productcategory ID 1776 and 1777 and product ID 708 is associated with 10 and 625 respectively. It is Product ID 707 and 708 that are related as the different size of the item.
There's quite a few items in teh database so manually going through the table isn't an ideal option - more of a last resort.