You can increase the size of an image (which in turn increases the pixels, as that refers to the size of the image), but to do so often means poorer image quality.
The best thing to do is either set your camera to take images of a certain size, while allowing enough for trims etc to be made. Basic image editing is quite easy and there are a lot of free software programs out there that will allow you to crop and resize images before uploading them. (If anyone would like to know how to do it in either Microsoft Paint or Photofiltre, I'll post some quick instructions here - I usually take images the maximum size my camera allows, which gives me a picture about 3800 x 2700 pixels before editing, then I frame a square image and crop the excess, then resize to a 1000 x 1000 pixel image to make full use of the gallery image.
For some other photo editing tips, like how to remove backgrounds using Photofiltre, syrupsmummy posted this great tutorial a few months ago: http://community.ebay.com.au/topic/Selling/Background-Listing-Pictures/500153202?start=0
The orange flag will appear on any image that doesn't have a side that is at least 1000 pixels, so even if you have a 500 x 500 pixel image you'll still get the note saying it's not to eBay's recommended size.
