The lack of ground connection was the cause of my gibberish serial output, at a time I thought my module was faulty then noticed what I had done.
Was sure that was the cause of your problem as your reply sounded like you failed to connected the ground lines on your sim800 and microcontroller.
Try a simple sketch to see if AT commands work as expected.
If that still doesn't work, hopefully others with more experience can help you solve this problem. That was the only thing I could think of.