I think I might be having a similar issue with my openvpn connect (not to nordvpn). On my nexus 5 the vpn works fine on wifi and cell service. On my nexus 7 and pinphone using the same keys, certs and settings the vpn connects fine and the routes update but I can't get to the internet. Only difference I saw was that on the nexus 5 (the working connection) the first "default via" entry was for my local router and the second was for the vpn's internal address but on the other devices they were switched around.
The only time I've noticed the nexus 5 not working is if I set up the vpn and the let the phone go to sleep. When I start it back up sometimes I don't have internet access until I turn the vpn connection off and on again.
I'll play around and see if I can spot what's different between them.