In an earlier comment to a posting where I was lamenting my lack of skill at drawing graphics for Metal Glove, Charlie (of Freegamer fame) suggested I give the Free Art Search tool a go, so I did.
And it's pretty good. After only a few minutes I came across the solution to my problems: Battle for Wesnoth (one of the best FOSS games out there) has excellent graphics, and they have been released under GPL! So, IANAL but I think that means that I can use them as long as I give full credit, and release my software under GPL, which I do anyway.
So my next task is to replace all the graphics for those from Wesnoth. I originally used the graphics from a game called Wyvern, but the license is unknown, and I received no reply from the author.
Once this is done, I can finally release it!