Default Google Now not showing cards

Hi, I recently factory reset my device, and now Google now is not showing its cards, when I go to the settings Google Now is off and there's a message under it saying "Google Now requires location services which are not available", I got GPS working and everything else is pretty normal, it used to work before... What seems to be the problem? I'm on android 4.3.