Funny I was looking for Coppermine
SEO stuff and this was the first thing that came up.
To be honest I've been using Coppermine for a while and its not so much the URL's that are the problem although it does help to switch it on.
You want to pay attention to your template more. If you are handy with PHP CSS and XHTML you can get it to play a bit nicer. Images should have alt and title attributes that describe the image.
This along with the correct title tag for each (don't confuse title tag and title attribute) should help.
I have been meaning to do this for a while, but just don't have the time. Its a lower priority at the moment.
Anyhow I hope that helps.