well, the first problem I noticed was that the image looks stretched. I know you're going for a tall-pixel look, but it looks like you drew most of it with square pixels, then stretched it vertically.
I really like the watch. Personally, I like it without a background. The tileset is nice too. The underwater part looks nice, though it might be hard to navigate. Is there a ceiling?
Anyway, I like the EGA palette. It may seem hard to work with, but I think it can be a lot of fun.