I make custom borders all the time using the stamp tool and somtimes brushes. In Photoshop CS - first create a new layer. If you use the marquee tool to create the outer frame box and then use it again to create the inner frame for the border (choosing the 3rd from left choice of removing the inner contents - see tool bar) you now have the border frame to play w/your design in.
For the design - choose any design you like from a photo - select it copy- paste it in a new window - here is where you can have a lot of fun - playing with filters, colors, shapeing - when you are done save it by itself - usually for the frame it needs to be rather small so now save at smaller sizes - select all - under Edit - Define Pattern - and now it becomes a stamp you can choose from your presets stamps. Back to your original frame - and paint in the stamp.
I have discovered that you can combine these stamps with the brush tool for other effects. Say paint a border line on the inside and outside of the frame (holding the shift key while you stroke) and using the stamp down the center. The number of patterns and designs you can come up with is limitless and so much fun in the process. Of course after you paint your design you can always use the Layer style adjustment to play with countless other things!
In this way you can customize your certificate borders to include things that may be meaningful to the certificate - such as a logo - a design from the program - even just color or shape. Have fun with it!