Google Now Error topic

I bought the One plus One a few days ago and when I tried to set up Google Now, it gave me "Check your network and try again" error. I've tried clearing cache and data and even a complete factory reset. The issue is not the connection as everything else is working perfectly and Google Now is working perfectly on another Nexus 4 and Galaxy S5 I own. Any help on this issue would be appreciated