System Status: Error "Cron Not Running" after update to 4.7.4
A similar-sounding bug report has been filed here:

https://issues.civicrm.org/jira/browse/CRM-18514

There are scattered reports of cron-related issues in 4.7 but people have been not giving detailed enough information to really pin the problem down. Can you say exactly how you have your Civi cron jobs configured to run? From your question it is not clear that you ever had cron set up correctly... the warning message about that is a new feature in 4.7 - it may simply be telling you about a problem that's been there all along.