Could you list the versions of ...

• perl & DBD::Sybase;
• the external libraries (e.g. freetds or ones from AES) that DBD::Sybase uses;
• isql;
• Replication Server

You could do DBI->trace(4); before connect() to see where the issue is at more granular level.

At this point all I can say is to check that encrypted passwords match as sent by isql & DBD::Sybase (say, via tcpdump or some other network packet analyzer) to the replication server.