One thing I've done in the past (which you may have already tried): if the RUN animation isn't too long (less than half a sec before it loops), you could wait until it reaches its beginning (transitional) frame before stopping.
For example:
-- If Player is Stopped & RUN is Playing & RUN animation frame is 0
---- Set animation to STOPPED
The issue with this is that he'll run a little in place before he becomes truly idle. The longer your run animation, the worse it'll look. Often times, you'll have multiple identical (or similar) frames in your RUN animation. If so, you can improve the result by testing to see if it's any of these frames rather than just the first one. If your player has deceleration (i.e He gradually comes to a stop when there's no input), then this could look pretty decent if you start the transition while he's slowing down.
A more complex approach (just throwing it out there, don't know if it'll look good) would be to locate an appropriate transitional frame, and then animate the character towards that frame. For example, if the character's walk is 10 frames long, but he is two frames past the ideal transitional frame, reverse the animation, and then stop it once he's at the right frame. If, on the other hand, he is 8 frames in, let it play out until it loops. Find the closest distance and change the animation accordingly.
Don't know if that gives you any ideas at all :P