Symptoms

After deployment via MMC, workflows will not start and cannot start them manually. When you go to K2 workflows for a list item to start a workflow it says that my workflow does not exist on the server.
 

Diagnoses

Since the Package was deployed using MMC the only user that has rights on the WF is the K2 Service account. The error is misleading and should read that the user doesnt have start rights.
 

Resolution

Granted Admin rights to the correct accounts.
We have logged the Error message enhancement that error should state that the user (Mentioning username) does not have start rights.