Looking closer, I found that the culprit is a call to the stat() function of the SFTPFile instance within the prefetch() function of that same SFTPFile instance. I'm not sure if this is a problem with the server or the implementation of paramiko. 
That call to SFTPFile.stat() from SFTPFile.prefetch() is to get the file size. Right before prefetch() is called from get() the size is obtained through a SFTPClient.stat(remotepath) call. So my solution is:

- add an optional parameter size=None to prefetch()
- use size as a condition to get the file size or not:
  if size is None:
          size = self.stat().st_size
- in get(), pass the file_size variable that's already there as the size to use:
   fr.prefetch(file_size)

I don't get why the size is pulled twice consecutively from the server. I'm not sure if all if prefetch() is called from other places or if it will work in other scenarios when the size is not passed, but for know I just need to GET and PUT, and this solves my problem.

Full modified source:

In class SFTPClient...

def get(self, remotepath, localpath, callback=None):
        """
        Copy a remote file (C{remotepath}) from the SFTP server to the local
        host as C{localpath}.  Any exception raised by operations will be
        passed through.  This method is primarily provided as a convenience.

        @param remotepath: the remote file to copy
        @type remotepath: str
        @param localpath: the destination path on the local host
        @type localpath: str
        @param callback: optional callback function that accepts the bytes
            transferred so far and the total bytes to be transferred
            (since 1.7.4)
        @type callback: function(int, int)

        @since: 1.4
        """
        fr = self.file(remotepath, 'rb')
        file_size = self.stat(remotepath).st_size
        fr.prefetch(file_size)    # Pass file_size as parameter
        try:
            fl = file(localpath, 'wb')
            try:
                size = 0
                while True:
                    data = fr.read(32768)
                    if len(data) == 0:
                        break
                    fl.write(data)
                    size += len(data)
                    if callback is not None:
                        callback(size, file_size)
            finally:
                fl.close()
        finally:
            fr.close()
        s = os.stat(localpath)
        if s.st_size != size:
            raise IOError('size mismatch in get!  %d != %d' % (s.st_size, size))


In class SFTPFile....

def prefetch(self, size=None):            # add a size parameter
        """
        Pre-fetch the remaining contents of this file in anticipation of
        future L{read} calls.  If reading the entire file, pre-fetching can
        dramatically improve the download speed by avoiding roundtrip latency.
        The file's contents are incrementally buffered in a background thread.
        
        The prefetched data is stored in a buffer until read via the L{read}
        method.  Once data has been read, it's removed from the buffer.  The
        data may be read in a random order (using L{seek}); chunks of the
        buffer that haven't been read will continue to be buffered.

        @since: 1.5.1
        """
        if size is None:                   # if size was passed, skip stat() call
          size = self.stat().st_size
        # queue up async reads for the rest of the file
        chunks = []
        n = self._realpos
        while n < size:
            chunk = min(self.MAX_REQUEST_SIZE, size - n)
            chunks.append((n, chunk))
            n += chunk
        if len(chunks) > 0:
            self._start_prefetch(chunks)