Ok, thanks for the additional pictures. I figured this is the type of thing you were talking about, but I just couldn't spot the problem in your initial pictures.
Hopefully you understood the explanation for why this is happening at the bottom of my last post. One option you have for supporting additional resolutions is to just create different sets of sprites for them. For example, use one set of sprites for multiples of 1024x768 resolution, but if the user changes to 1920x1200, you can swap out your sprites for ones designed for that size. This would be more work of course, but it will allow you to support more resolution without worrying about how your sprites will looked when scaled.