had a quick look at the SD lib (in your arduino path) and the exists function calls the walkpath(...) function to walk the tree to see if it exists. What I saw it traverses the whole directory so some pointers might be at the end.
can you try rewindDirectory() ?
Which version of the Arduino are you using BTW?