I would try using a module such as HTTP::Recorder or WWW::Mechanize::Shell to record a successful manual form submission. The output of HTTP::Recorder, for instance, can be "dropped" right into your WWW::Mechanize scripts.

Another important tool for finding out what is really happening behind the scenes between server and browser is a protocol analyzer such as Ethereal.

HTH,