Okay, let's start from the top.

What paint program are you using?

Alright.  Start with finding everything that is necessary for the texture, such as rivets, windows, and such and isolating them.  Make that a new layer on your texture, and after you have everything that matters, simply delete the old texture from the picture.  Now just paint over what you have, making the layers "multiply" over the others.  This will keep the prevalent parts on the texture, but change the overall appearence of the image.

I hope this made sense.  I've been to the pub tonight, so I might not be in the best form! (dumb-fool grin).

First off, the default 2k4 737 is most likely just the one from 2k2 with a couple of extra lines in the aircraft.cfg, in which case you should be able to use any paint scheme from 2k2 in 2k4 on it.  I am not positive about that, but it seems awfully likely.  There might also be a painting template for that aircraft out somewhere.  I would search several FS sites, looking for 737 painting template.

Second, use the zoom feature that is part of the arrow tool to get a better view of the stuff you're working on.  Zoom in to about 3:1 or 4:1 and that will give you an easier time of isolating the rivets and such.

After you eventually do get the stuff isolated, select one certain part of the aircraft's rivets and seams and stuff that should all be the same color.  Now go up to where it says "colors" in the menu bar and select "Adjust" and then "Red/Green/Blue".  Now start fiddling with the values that come up in the viewbox.  The view on the left is what the picture looks like now.  The view on the right is what the picture will look like if you apply the settings you have entered.  Once you have the colors right, just click "OK" and it will be applied to only what you have selected.

Now, keep in mind: everything I have just told you is from a slightly older version of PSP, so it may not be the same as PSP 7.  If not, I would suggest looking at the repainting tutorial in my signature.