I had the same problem after switching to Emacs 24.3. The solution was to upgrade to the latest Tramp 2.2.7. Here is what I did:
- downloaded http://ftp.gnu.org/gnu/tramp/tramp-2.2.7.tar.gz
- unpacked the archive to my ~/.emacs.d/src. I am using emacs-starter-kit which adds this directory and all its subdirectories to the load-path. Otherwise follow the instructions in the Tramp's INSTALL file.
- used Cygwin bash to configure and compile the files. I don't use Cygwin's Emacs normally but it is convenient to have it for occasions like this.
- deleted the old tramp's el and elc files in my emacs/lisp/net for safety.
- restarted Emacs of course.
Do M-x tramp-version to make sure it is installed correctly. Now tramp works everywhere (dired, eshell, shell, etc).