I'm having the same issue on Nexus 5 (KitKat) and Nexus 9 (Lollipop).
On WiFi, Google Now won't update, it says "no connection". If I turn off the WiFi, it updates fine (over 3G).
The WiFi obviously works though, Play Store and Chrome and several games all connect over it without difficulty.