No, Flash on a MacBook Air can't play HD without stuttering. Flash imposes an enormous processing overhead. The GPU doesn't even enter into it because Flash 9 does not have GPU-accelerated video decoding. The same h.264 stream plays fine in native players on systems half as powerful.
To answer your question, with my current config (Ubuntu Eee 8.04) standard def plays fine. HD from sites like vimeo definitely stutters. Youtube does some sort of resolution detection and always gives a "this video has been removed" error for HD since it thinks I'm running at 800x480, even when I'm outputing solely to an external monitor (and I am certain the video exists).
The MacBook Air can't even play HD video without stuttering. How does your Eee hold up?
http://forums.macrumors.com/showthread.php?t=636511