This fixes it for me now, thank you.

Changes have been made in Git (master):

commit 8cd3093505c1805a1c2e7f9a41b0f47d145348ce
Author: Michael M Slusarz <slusarz@horde.org>
Date:   Thu Oct 17 07:02:28 2013 -0600

     Bug #12772

     Fix check for TLS, not only SSL

  .../Imap_Client/lib/Horde/Imap/Client/Socket.php   |   13 ++++++++-----
  framework/Smtp/lib/Horde/Smtp.php                  |   13 ++++++++-----
  2 files changed, 16 insertions(+), 10 deletions(-)

http://git.horde.org/horde-git/-/commit/8cd3093505c1805a1c2e7f9a41b0f47d145348ce

The problem is that since I am using TLS, 
Horde/Socket/Client::_connect will NOT set $this->_secure to true so 
the check in Horde_Imap_Client_Socket::_connect on line 557:

             if ($secure && !$this->_connection->secure) {
                 $this->setParam('secure', false);
             }

will always set 'secure' to false. Therefore, TLS will never be 
started in Horde_Imap_Client_Socket::_login.

Still same behavior, with the same workaround fixing it.

Changes have been made in Git (master):

commit 0e152ea608f548b6ba7ab2cb0b45247e146fc448
Author: Michael M Slusarz <slusarz@horde.org>
Date:   Wed Oct 16 23:15:05 2013 -0600

     Bug #12772

  .../Imap_Client/lib/Horde/Imap/Client/Socket.php   |    5 +++--
  framework/Smtp/lib/Horde/Smtp.php                  |    5 +++--
  2 files changed, 6 insertions(+), 4 deletions(-)

http://git.horde.org/horde-git/-/commit/0e152ea608f548b6ba7ab2cb0b45247e146fc448

In Horde_Imap_Client_Socket::_connect() the code:

             if (!$this->_connection->secure) {
                  $this->setParam('secure', false);
             }

seems to be called before TLS is started, and sets the secure 
parameter to false, so that in ::_login(), in the code to switch to 
TLS if not secure never gets called since $this->getParam('secure') 
will return false, and not 'tls' like I have configured.

Commenting out the code in _connect() that sets secure to false 
"fixes" it for me. No idea how to fix it properly.

I lied about the IMAP log, I had IMAP authentication enabled instead 
of Application/IMP.  With Application/IMP, I only get the following in 
the IMAP log:

------------------------------
S: * OK [CAPABILITY IMAP4rev1 LITERAL+ SASL-IR LOGIN-REFERRALS ID 
ENABLE IDLE STARTTLS LOGINDISABLED] Dovecot ready.

No IMAP log produced, no traffic with the IMAP server. Cleared all 
caches, disabled them. Git bisect shows this is the culprit:

mrubinsk@singularity:horde ((no branch, bisect started on master))$ 
git bisect good
227e17105ca4e5878f2110c5ade26a3163782a0b is the first bad commit
commit 227e17105ca4e5878f2110c5ade26a3163782a0b
Author: Michael M Slusarz <slusarz@horde.org>
Date:   Wed Oct 16 15:04:07 2013 -0600

     Use Socket_Client package

:040000 040000 ad07dc0dd1410a8b2247fc97847e6b79939da23a 
16ea6b04fb6f44ad0973a63b351bf8399fab84a7 M      framework

Horde_Imap_Client_Exception: No supported IMAP authentication method 
could be found. in 
/usr/local/horde/horde/framework/Imap_Client/lib/Horde/Imap/Client/Socket.php 
on line 452

Call Stack:
     0.0004     270792   1. {main}() /usr/local/horde/horde/horde/rpc.php:0
     0.2064   14564232   2. Horde_Rpc_ActiveSync->getResponse() 
/usr/local/horde/horde/horde/rpc.php:156
     0.2066   15617960   3. Horde_ActiveSync->handleRequest() 
/usr/local/horde/horde/framework/Rpc/lib/Horde/Rpc/ActiveSync.php:143
     0.2067   15623560   4. Horde_ActiveSync->authenticate() 
/usr/local/horde/horde/framework/ActiveSync/lib/Horde/ActiveSync.php:708
     0.2073   15647360   5. 
Horde_Core_ActiveSync_Driver->authenticate() 
/usr/local/horde/horde/framework/ActiveSync/lib/Horde/ActiveSync.php:547
     0.2074   15648192   6. Horde_Core_ActiveSync_Auth->authenticate() 
/usr/local/horde/horde/framework/Core/lib/Horde/Core/ActiveSync/Driver.php:201
     0.2074   15648312   7. 
Horde_Core_ActiveSync_Auth->_authenticate() 
/usr/local/horde/horde/framework/Core/lib/Horde/Core/ActiveSync/Auth.php:60
     0.2074   15648432   8. 
Horde_Core_Auth_Application->authenticate() 
/usr/local/horde/horde/framework/Core/lib/Horde/Core/ActiveSync/Auth.php:79
     0.2086   15650152   9. Horde_Auth_Base->authenticate() 
/usr/local/horde/horde/framework/Core/lib/Horde/Core/Auth/Application.php:127
     0.2086   15650632  10. Horde_Auth_Imap->_authenticate() 
/usr/local/horde/horde/framework/Auth/lib/Horde/Auth/Base.php:160
     0.2234   17314088  11. Horde_Imap_Client_Base->login() 
/usr/local/horde/horde/framework/Auth/lib/Horde/Auth/Imap.php:93
     0.2234   17314232  12. Horde_Imap_Client_Socket->_login() 
/usr/local/horde/horde/framework/Imap_Client/lib/Horde/Imap/Client/Base.php:790