Here's the actual reason for the problem: You need to use SSLv3 or TLS1 instead of TLS1.2 to connect to that server. This is probably why it worked when you used Net::SSL first; I believe it tries different ciphers in a way that WWW:Mechanize doesn't.
This is how I found it:
I tried connecting from several different servers, and I find that the ones that worked have an older SSL version. I then checked the difference between what ciphers are used in the versions, and tried connecting with different ciphers.
When I connect using TLS1.2, I get:
$ openssl s_client -connect www.imstores.com:443 -tls1_2
CONNECTED(00000003)
write:errno=54
---
no peer certificate available
---
No client certificate CA names sent
---
SSL handshake has read 0 bytes and written 322 bytes
---
New, (NONE), Cipher is (NONE)
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
---
But when I connect with SSLv3 or TLS1, I get:
$ openssl s_client -connect www.imstores.com:443 -tls1
CONNECTED(00000003)
depth=0 /serialNumber=O3gPUAuGGROuHEhlyLaeJfj7SOn6tFTx/C=US/O=www.imstores.com/OU=GT29846307/OU=See www.geotrust.com/resources/cps (c)11/OU=Domain Control Validated - QuickSSL(R) Premium/CN=www.imstores.com
verify error:num=20:unable to get local issuer certificate
[...and so on, including server certificate...]
Exactly how to make WWW:Mechanize use TLS1 or SSLv3 is left as an exercise to the student.