Because the Mint Software Centre allows users to add and remove software it sensibly requires root privileges before you can proceed. To do this it utilises gksu.
Specifically, the launcher in the menu looks like this;
The problem is that when you try to launch the MSC it asks for a password. Entering your user password (which has sudo privileges) does not work. This is because gksu is expecting the root user password, which with a default install does not exist.
The way to fix this is to tell gksu to use sudo for privilege excalation.
This will popup a dialog box like this;
Change the "Authentication Mode" from "su" to "sudo" and you are done!