I installed synaptic manually, after I noticed that after upgrade it was gone.
Also You can try aptitude, it was also part of Mint, I don't know right now if it still is (I guess You could install that manually too)
Ok, I think what we're supposed to do now is this: Go to the Update Manager>Edit>Software Sources>Maintenance and either "Remove foreign packages" or "downgrade foreign packages." I think this's been there for a while now, just never used it before.