I have a table of contents in a very big doc that was converted from Microsoft Word 2010. I was able to change the color of the text but, when I tried to drag and create the rectangle for the link - it just wouldn't let me. I ran the text recognition tool - it didn't recognize any of the text, even though this came from a Word doc.
[Moved from Comments forum to an Acrobat forum... Mod]
The two things are not related. You can create links over any kind of static content in a PDF file. It doesn't have to be above actual text.
What exactly happens when you try to use the Link tool? Is there an error message of some kind?