Linker error on ros kinetic + Ubuntu 16.04

edit

I am having trouble running catkin_make with the newest release of ROS. For any package I try to build from my catking workspace, I'm getting linker errors about undefined references to ROS core libraries.

For example, trying to build the gps_umd module from here http://wiki.ros.org/gps_umd :

I get the following errors:

[ 18%] Linking CXX executable /home/juancamilog/aqua_ws/devel/lib/gps_common/utm_odometry_node
CMakeFiles/gps_common/utm_odometry_node.dir/src/utm_odometry_node.cpp.o: In function `callback(boost::shared_ptr<sensor_msgs::NavSatFix_<std::allocator<void> > const> const&)':
utm_odometry_node.cpp:(.text+0xcd3): undefined reference to `ros::console::initializeLogLocation(ros::console::LogLocation*, std::string const&, ros::console::levels::Level)'
CMakeFiles/gps_common/utm_odometry_node.dir/src/utm_odometry_node.cpp.o: In function `main':
utm_odometry_node.cpp:(.text+0x1268): undefined reference to `ros::init(int&, char**, std::string const&, unsigned int)'
utm_odometry_node.cpp:(.text+0x12c4): undefined reference to `ros::NodeHandle::NodeHandle(std::string const&, std::map<std::string, std::string, std::less<std::string>, std::allocator<std::pair<std::string const, std::string> > > const&)'
utm_odometry_node.cpp:(.text+0x133b): undefined reference to `ros::NodeHandle::NodeHandle(std::string const&, std::map<std::string, std::string, std::less<std::string>, std::allocator<std::pair<std::string const, std::string> > > const&)'
CMakeFiles/gps_common/utm_odometry_node.dir/src/utm_odometry_node.cpp.o: In function `void ros::Publisher::publish<nav_msgs::Odometry_<std::allocator<void> > >(nav_msgs::Odometry_<std::allocator<void> > const&) const':
utm_odometry_node.cpp:(.text._ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_[_ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_]+0xa0): undefined reference to `ros::console::initializeLogLocation(ros::console::LogLocation*, std::string const&, ros::console::levels::Level)'
utm_odometry_node.cpp:(.text._ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_[_ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_]+0x1a3): undefined reference to `ros::console::initializeLogLocation(ros::console::LogLocation*, std::string const&, ros::console::levels::Level)'
utm_odometry_node.cpp:(.text._ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_[_ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_]+0x29e): undefined reference to `ros::console::initializeLogLocation(ros::console::LogLocation*, std::string const&, ros::console::levels::Level)'
utm_odometry_node.cpp:(.text._ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_[_ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_]+0x3c1): undefined reference to `ros::console::initializeLogLocation(ros::console::LogLocation*, std::string const&, ros::console::levels::Level)'
utm_odometry_node.cpp:(.text._ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_[_ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_]+0x4c4): undefined reference to `ros::console::initializeLogLocation(ros::console::LogLocation*, std::string const&, ros::console::levels::Level)'
CMakeFiles/gps_common/utm_odometry_node.dir/src/utm_odometry_node.cpp.o:utm_odometry_node.cpp:(.text._ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_[_ZNK3ros9Publisher7publishIN8nav_msgs9Odometry_ISaIvEEEEEvRKT_]+0x5d6): more undefined references to `ros::console::initializeLogLocation(ros::console::LogLocation*, std::string const&, ros::console::levels::Level)' follow
CMakeFiles/gps_common/utm_odometry_node.dir/src/utm_odometry_node.cpp.o: In function `bool ros::NodeHandle::param<std::string>(std::string const&, std::string&, std::string const&) const':
utm_odometry_node.cpp:(.text._ZNK3ros10NodeHandle5paramISsEEbRKSsRT_RKS4_[_ZNK3ros10NodeHandle5paramISsEEbRKSsRT_RKS4_]+0x27): undefined reference to `ros::NodeHandle::hasParam(std::string const&) const'
utm_odometry_node.cpp:(.text._ZNK3ros10NodeHandle5paramISsEEbRKSsRT_RKS4_[_ZNK3ros10NodeHandle5paramISsEEbRKSsRT_RKS4_]+0x42): undefined reference to `ros::NodeHandle::getParam(std::string const&, std::string&) const'
CMakeFiles/gps_common/utm_odometry_node.dir/src/utm_odometry_node.cpp.o: In function `bool ros::NodeHandle::param<double>(std::string const&, double&, double const&) const':
utm_odometry_node.cpp:(.text._ZNK3ros10NodeHandle5paramIdEEbRKSsRT_RKS4_[_ZNK3ros10NodeHandle5paramIdEEbRKSsRT_RKS4_]+0x27): undefined reference to `ros::NodeHandle::hasParam(std::string const&) const'
utm_odometry_node.cpp:(.text._ZNK3ros10NodeHandle5paramIdEEbRKSsRT_RKS4_[_ZNK3ros10NodeHandle5paramIdEEbRKSsRT_RKS4_]+0x42): undefined reference to `ros::NodeHandle::getParam(std::string const&, double&) const'
CMakeFiles/gps_common/utm_odometry_node.dir/src/utm_odometry_node.cpp.o: In function `ros::SubscriptionCallbackHelperT<boost::shared_ptr<sensor_msgs::NavSatFix_<std::allocator<void ...