Bill T (New Mexico) , Jun 24, 2006; 07:15 p.m.
If you are using the Edit->Stroke command, you may be trying to create a border outside the available image area, which doesn't work.
Select->All (there must be some selection for Stroke to work)
Be sure "Inside" is selected, pick a color and a pixel width.
If you go to Select->Modify->Border you can conveniently reduce the selection size in steps, which is helpful in building up fancy boarders.