If you decide exactly which part of the link needs to change you should be able to do this.
Code:
Sub change_path()
Dim osld As Slide
Dim oshp As Shape
For Each osld In ActivePresentation.Slides
For Each oshp In osld.Shapes
If oshp.Type = msoMedia Then
If oshp.MediaType = ppMediaTypeMovie Then
On Error Resume Next ' in case there are embedded videos
If oshp.LinkFormat.SourceFullName <> "" Then
'original was C:\users\John\Desktop\MyVids\vid.wmv
'new path is C:\users\John\Desktop\MyNewVids\vid.wmv
oshp.LinkFormat.SourceFullName = Replace(oshp.LinkFormat.SourceFullName, Find:="MyVids", Replace:="MyNewVids")
End If
End If
End If
Next oshp
Next osld
End Sub