Hi @zichrist
I don't own a NVIDIA Shield but I would imagine the NOW App should be still available on the Google Apps Store or under the Apps Store directly on the device.
Couple of things might be causing the problem, such has a VPN or the wrong region on your Shield.
Also use something like what's my IP address to make sure your Router can be found by NOW from within the UK.
Also because the clock's went forward an hour on Sunday, check the time zone and date on your Shield.
Hopefully other Shield owners will offer more suggestions.