I haven’t tested the driver with an OEM718D, but I think it should work. Make sure you set the polling_period param correctly; I believe the default is 0.05, but if your GPS is running at 5 Hz, then it should be 0.20.
Actually, I think there may be a bug that causes the “insufficient data rate” warning to be logged if your GPS produces GPGGA logs at a rate less than 20 Hz, even if your polling_period is configured differently. I’ll look into that. If it is working properly, you should see it publish gps_common/GPSFix messages on the gps topic at your expected rate.
As for your other problem, are you sure you sourced ROS’s setup.bash in the same terminal you ran rosecho in after you installed the packages? I tested it on a fresh Ubuntu 14.04 / ROS Jade system, and running rosmsg show novatel_gps_msgs/NovatelPosition worked for me.