The linux system call stat() (stat(3) in linux man page) can return < 0 when invoked over a file or directory that reside in a not properly configured filesystem (observed in misconfigured permission on fuse).
In that case stat() fail even if a directory exists, so cding to those directories fails and file/folder autocompletion (and probably every time fish use stat() in the filesystem) fails as well.
As reported and tested on gitter, access() apparently works, as does actually changing the directory.
The following branch solves the cd problem, but there is still work to do to get autocompletion to properly work.