Got this error when I was trying to rebuild a site from scratch. I had a clean install of Joomla and had imported the content and category tables from another site.
I received this error: "Save failed with the following error: Invalid parent ID." when I tried to edit one of the articles.
Solution.
1. Click 'rebuild' in menu manager.
2. Click 'rebuild' in categories manager.
3. Open Categories (top categories first, then sub-categories) and save them
I don't know what exactly this fixed but it worked.