System.InvalidOperationException: Request format is unrecognized for URL unexpectedly ending in '/MethodName'It turns out it's another web.config setting (which makes sense) where you have to specify the required protocols. Here is the code:
<webServices>
<protocols>
<add name="HttpGet"/>
<add name="HttpPost"/>
</protocols>
</webServices>