If your beautiful taxonomies were working perfectly and you upgraded to wordpress 3.5 and all of the sudden,
When the post is published I get the message “This is somewhat embarrassing, isn’t it?
it is because wordpress made some changes to the permalinks
Go to Settings / Permalinks and select post name or other format
For me it does not work using these Permalinks as Published:-
So just change that selection and give it a try