Do you also need to capture the closing [/video] tag?
If you only want to capture what you posted up...try this...
Quick Find: [video=youtube;
Regular expression: #\[video=youtube\;([a-z0-9]+)\]http.+\/watch.+v=[a-z0-9]+#siu
Replacement String: [media=youtube]\1[/media]
If you also need to capture the [/video] tag,
example:
[video=youtube;fn7BRf7XSsU]http://www.youtube.com/watch?feature=player_embedded&v=fn7BRf7XSsU[/video]
you can use this instead for the
Regular expression:
#\[video=youtube\;([a-z0-9]+)\]http.+\/watch.+v=[a-z0-9]+\[\/video\]#siu
Edited: note to self...remember to use plain tags before posting things that will parse :-/