After ruling out the obvious, I used Charles proxy to see the decrypted request each method was making and it looks like AnyEvent::HTTP is probably mangling the request.
This is what the working request looks like:
POST /post HTTP/1.1
TE: deflate,gzip;q=0.3
Connection: TE, close
Accept-Encoding: gzip
Host: h.wrttn.me
User-Agent: WWW-Mechanize/1.72
Content-Type: application/x-www-form-urlencoded
Rest-Key: key
Rest-Sign: eZsAHbbDBmD3/vHe7zg8IDdPJlV8WHBgHiAdd+ZDb8cD9TPHza4liDAYiLM
+52nHLaGF2Jb9hlpoF 72SfxUg1Uw==
Content-Length: 34
pass=&nonce=1351623186546267&name=
And this is the mangled request from AnyEvent::HTTP:
POST /post HTTP/1.1
User-agent: Mozilla/5.0 (compatible; U; AnyEvent-HTTP/2.14; +http://so
+ftware.schmorp.de/pkg/AnyEvent)
Connection: close Te
Rest-sign: GvzSzGg5WHPpL4O2bw48Q8lX6O5prasaiysH98FVS9oWYNfcs7pdUtWNpm7
+xGYG8zT3e0/BcPgHP LZWzMTdubg==
I see the same behavior when changing from https to http.