In PSE, go to FILE -> Save For Web
** You'll get a message about the file size exceeding size save for web was designed for, etc ... click Yes to continue
To the far right, modify the file type to JPEG, and then the size to 600 x 600. Make sure the "Constrain Proportions" box is checked.
Then click OK, and give your file a name.
This file will then be the correct size to upload to the gallery.
Hope this helps!