In Keynote, when adding a frame stroke, it is possible to change the background color.
However I am not seeing any way to change the actual color of the frame border (which always stays white).
Any advice for doing so?
While you can't change the color of a picture frame, you CAN use line instead. It has the standard color well for setting the color; you can use any width for the line. 24 px looks similar to the basic picture frame. And you can use various line styles for the edge. This is substantially easier than the double box method.
In addition, you can do this on a template with those media replacement place holders, and it will be done in descendent masters.
As far as I can see, the answer would have to be no.
The options for changing the colours of picture frames are greyed out, and in all the many keynotes I have seen, green frames have never been included.
That is not to say it is impossible.
It may be possible to make one, like this.
Create a rectangle of a shade of colour 50% brighter than the desired shade. Create two identically sized photos the first with a frame. Set the framed photo to 50% opacity, and position it over the rectangle. Finally, place the good photo over the frame, and hope it was worth the effort.
I hope this helps, somehow.