I have managed to fix the original problem, but I do have another.
For anybody wishing to know, I had been exporting to Adobe PDF Reader version 4 and above. I fixed the problem by exporting to version 5 and above instead, and now the links all work again (odd, but true).
In order to highlight a link, in InDesign I highlight the 'link-text', underline it and change the colour manually to blue (R=0, G=0, B=255). However, some of the links turn into a good blue colour, whilst others turn out a dullish purple, eventhough I use the same settings each time.
Any ideas on this one?