Thanks for responding. After some back and forth with support, I figured out what the problem was. I had a base URL defined as a macro. When you have a macro in this field and create links from the site tree, the tracking statistics will not work. The solution is either to have no value in the base URL configuration or hardcode it if your use case is a different URL to the Kentico install.
Kentico support said they would not be fixing this behaviour. I think they should at least update the documentation to alert users of this use case. I still think it is a bug albeit with a work around.