Try to find out where your theme is overriding the thumbnail sizes, otherwise things will get messy. Another way would be to override the thumbnail sizes through code but if your theme is overriding the default sizes, you will have to mess around with priorities and hooks. Try running a search on your theme (in a code editor) for the word "thumbnail" or "medium". That should help you isolate the issue.
Another option is to register new image sizes and use these for the gallery using WordPress' add_image_size function. http://codex.wordpress.org/Function_Reference/add_image_size
If you go this route, I can provide you with the neccessary code to paste into your theme, which will allow the gallery to use this new size you have created.