Consumer GPS devices do not work above 18 km, so unfortunately even without the cell reception limitations he would not have been able to track the balloon during it's entire voyage. (They also don't work when travelling faster than 1000 mph. I believe the limitations are to prevent consumer GPS hardware from being used in things like missiles.)
I hope he manages to recover everything alright.