Are you powering SIM800 with 4V? I had something like that because i forgot to add a diode to lower the voltage from 5V.
Also check your APN name, those messages showed are when code is trying to set APN.
And if using an external power source, don't forget to connect a common GROUND between power source and arduino