When do offer letters usually arrive? I contacted a professor about working on research with him. I met with him in person and he let me know he wanted to work with me, that he would be my research advisor, and if I applied to the department he would get funding for me. I applied to the university, got accepted into the program then filled out a TA application.

I was informed by my research advisor that I was selected as a TA and that I would receive my offer letter soon in the mail. It has been several months since I was told that and he checked on the delay and said that the TA offer letters were being held up in the provost's office for some reason. Classes start in August and I still haven't received my offer letter. Is this sort of thing common, or should I start to worry? My research advisor has guaranteed me I will be funded and I have nothing to worry about.
You are in a tough position because 'offers' cannot be guaranteed until you have an official letter in hand.  And, when letters are sent is really specific to a department and university.  For example, when I was accepted to graduate school, the acceptance letter and funding were part of the same letter.