I don't have a lot of experience with threads, but I did run your sample program (thanks for that!) and made a little investigation.
My best guess is that this is a problem with the Net::Telnet module. My reason for reaching this conclusion is that the error message returned, "Failed to get first prompt", is returned *immediately* after the connect() method is called. There should be a 10 second timeout on this, waiting for the prompt. The timeout actually happens within the waitfor() method of Net::Telnet, so I think it's this which is not thread safe. For some reason it does not wait 10 seconds but instead returns immediately with a failure. Perhaps it is some problem with signal handling?
Unfortunately, the loop which has the "broken" timeout in Net::Telnet is generated code, so it's hard to debug, and also because I am not an experienced threads programmer I wouldn't know where to start anyway.
For now, I think we are going to have to say that Net::Appliance::Session is not thread safe, because of this problem. I'm very sorry about that.