Depending on which version you're coming from: Link categories now have their own permissions. So like with stories and topics, if you don't have the proper permissions to view a category, you won't see the links in that category.
Could that be it?
I'm having the same issue. Logged in users can see the links, stories, and files.... but anonymous users who do not login see nothing new in the What's new block.
The Links in my What New block have gone missing what is the solution ?