Custom Post Type Permalinks with %category%

I can’t comment on your scripts, but if you change anything related to permalinks – it is always advisable to go to the Dashboard -> Settings -> Permalinks and click the “Update” button. This tells WordPress to flush its rewrite rules. If your script is correct, then after doing the “Update” – you won’t get 404 errors.