People have been having all sorts of troubles with gmail because of recent authorisation changes.
Your slow email sounds like it might be a result of Grey Listing. This is a process where email is delayed until a reputation is built up. Unfortunately it can be affected by other domains sharing the same IP.
Have you talked to the hosting provider about it?