Could you list the versions of ...
- perl & DBD::Sybase;
- the external libraries (e.g. freetds or ones from AES) that DBD::Sybase uses;
- 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.