I don't know Visio so only a basic question from me.
When you "Save as", where do you save to?
If you save to the same folder as you were working from then I can't help. But if you are changing directories at the Save As stage, then any relative link might fail.
Don't know about absolute links, but that does seem strange. When you hover over an absolute link in the saved PDF, does the link read true? And is the target still where it is supposed to be?
There may be some particular method of inserting these links in Visio, but I will have to leave that to others.
Mark
I have added a link to some shapes within my Visio drawing. From within Visio itself the link works (whether the linked file is a pdf or another Visio drawing).
When I use the Save As feature to save the Visio drawing as a pdf the link is present in the pdf drawing but the file does not open. Instead I receive an error message that the file can't be found.
This same problem happens whether I use relative or absolute locations.

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic