The solution is pretty simple, just add the support(in bold) for the httpPost protocol in your web.config file:

<?xml version="1.0" encoding="utf-8"?>
<configuration xmlns="http://schemas.microsoft.com/.NetConfiguration/v2.0">
    <system.web>
       <webServices>  
        <protocols>   
            <add name="HttpPost"/>  
        </protocols> 
       </webServices>
    </system.web>
</configuration>

Publishing the WebService do not automatically add these lines so you'll have to do it manually.