Blacklisted IP address\domain name - what to do?

[la chupacabra]

Hello All,
I'm having a lot of trouble with my client's email account (hosted by Gmail), more than a week ago it stopped sending and receiving emails, without any error messages. I did some research and apparently the IP address and maybe domain have been black listed.
I checked all computers on the network for malware and they are clean.
I checked that if I login to that Gmail account from different network, I can see new emails, but not from the office network.
How can I fix it?
I contacted Google and they claim that everything is OK on their side.
I've also contacted BT Broadband to change my IP address and also to make it static (it was dynamic before). Now I'm waiting 24 hours for them to set it up.
Is changing IP going to solve the problem? I've checked that the domain name is also blacklisted.

 

[mgolus]

I would verify that nothing changed with the Client's domain name that is linked to gmail and make sure the MX record on the domain name is correctly pointing to gmail's server. Since they aren't receiving mail either, it leads me to believe that blacklisting wouldn't be an issue (even if it was, emails sent out should still get to the recipient, but may just go to the spam/junk folder).

 

[dark_lord69]

Sound like it's being blocked by the IT department or a firewall.

 

[la chupacabra]

It's a small office network, 4 PCs connected to the router and BT broadband over telephone line, so it wasn't blocked by IT department, nor firewall (I checked).
Like I said no emails can be sent from this network and no emails can be received, but they they seem to be working when send\receive from diffrent network (i.e mobile or computer connected to another router in different office).
Nothing has changed in a domain name, but we did transfer the website to a different web hosting company (GoDaddy).
I was told by Google technician that everything is OK on their side and it should work fine once we change the IP address. I'm just a bit worried that it won't be enough, because I've checked that besides blacklisted IP address on sites like Spamhaus, there is also blacklisted domain name of the email address that we use.