Either the library you were using was terrible, your servers were powered by hamsters, or you were feeding the wrong parameters into the algorithm.

The code below takes ~15 seconds on 1 year old MacBook running Java 1.8.0_111-b14 and uses no 3rd party libraries:

        PBEKeySpec spec = new PBEKeySpec(password.toCharArray(), salt, 10_000_000, 256);
        SecretKeyFactory skf = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA256");     
        byte[] hash = skf.generateSecret(spec).getEncoded();