+1 for removing those protocol methods.
FileSystem#exists() should probably be made a concrete method in FileSystem.java, defined in terms of getFileStatus(), most existing implementations can probably be removed, and it could probably be deprecated.
BTW, what is getFileStatus() supposed to do when a file does not exist? Throw an IOException or return null? The former is generally preferable, but the latter makes implementing exists() easier, since we should not use exception handling for normal program flow.
I don't see a need to do this the day before 0.16 feature freeze, and it could be destabilizing.