Update: Valve has issued a statement indicating that it is aware of the block and working to address it.
"Right now players in Malaysia can access the games they own on Steam, but the Steam Store is being blocked by some local telcos in Malaysia. From reports we are reading, this is due to a single game that conflicts with local laws," a rep said. "We have contacted the developer, removed the game, and are attempting to make contact with the officials in Malaysia to remove the block. We apologize for any inconvenience."
The removal of Fight of Gods appears to only be in effect in Malaysia, however, as it's currently still available for purchase in the US and elsewhere.
I can now access Steam on TM's Unifi fibre broadband, but MyMaxis (mobile internet) is still giving me a "404 - file or directory not found". At this stage, I would definintely say it is in the process of propogating the unblock, and to just give it a bit longer.