First off, update to 6.0.1
Do a factory reset.
Get a fresh Nano SIM from Ufone.
Turn the phone off.
Pop the SIM in and make sure the tray fits in properly and the SIM isn't wiggling around.
Put the phone back on.
Quickly dial *#*#4636#*#*
Press Phone Information
Turn Radio Off
Choose WCDMA/GSM (Auto) if you're in 3G coverage
Choose GSM only if you're not in 3G coverage
Once you've selected the option, turn the radio back on and quickly reboot the phone.
You should have signal. If not, then let Google know the problem.
As a last resort, try another SIM from a different network.