If you just want colored borders, I'll show you two ways that I do it. Let me go take some screenshots. I use CS3 on my mac.

Alright, one way.

Open the picture and go to Image > Canvas size.
Very large picture
Change the scale to pixels, it makes it easier. Decide how many pixels you want on each side ad double that number. Type it into both the width and height boxes and click ok.


You can change the color of the canvas now if you want but I do that later.
This is what you get.

Now, use the magic wand tool to select the border, copy and paste it, so you should get this.


Select the border and go to Image > Adjustments > Hue/Saturation
large picture
move the sliders back and forth until you get the color you want.
Then you can use layer styles to do things to it. To do this you can go to Layer > Layer styles and click one and experiment.

I repeated the process to get this.