Turns out there is a simple way to accomplish gradients on borders. That took me longer than it should have to arrive at though, this screencast covers all the ways I tried and looked at along the way.
Note: In the video, I ended with the sentiment that the border-image plus linear-gradient was the best way. I still think that, but I failed to mention it's only supported in WebKit, despite Firefox and Opera supporting both of these properties (together they fail). The new demo page lists all techniques so you can decide which one might work best for you yourself.
*May or may not contain any actual "CSS" or "Tricks".