I can't reproduce in Office XP, so I guess Office XP is one solution.
Another possible solution in to make sure to save the spreadsheet in a different directory than the hyperlink target, possibly forcing Excel to keep the entire path.
Or try:
ActiveSheet.Hyperlinks.Add Anchor:=Selection, _
Address:="file:///C:\SomeFolder\Doc.doc"