Have you tried deleting the link in your dock, and re-creating it from the application?
You could also check the properties of the link to make sure it is pointing to the correct application.
If it still doesn't work, there might be a permissions problem -- although if other applications are starting up from the Dock, then Parallels should work too. You could try a "Repair Permissions" anyway.