We have a crazy live chat queue and have the Target wait time and Max wait time set really high

Yeah the issue we're facing is if all agents are busy the chat is just instantly rejected with the message, so our wait time isn't coming into play

Are the Agents in the Available state?

No thats the issue, when no agents are available customers are instantly kicked out of the chat.  Really you want the customer to land in a queue so you have the opportunity to free up an agent and answer - just like any phone line.

If there are no agents with the "Available" status, the chat queue is closed so the users get that message.

We have our Agents manually go offline when they are scheduled to leave chat support.  We have the max chat per agent set to 3, so if one goes under 3, the AWA routes the next chat to that person.  If that Agent cannot accept the chat, AWA looks for the next available agent and leaves that status to Available.  

I have seen our chat queue go up to 30 people (it was a rough day)

If ALL agents get set to anything other than Available, your chat closes.