As Twitter now requires the usage of OAuth to register new applications, I was looking into this as well. Luckily, Twitter4j has support for OAuth.
Unfortunately this did not work for me ;-(
After some digging, I found the solution (code is the one from the samples page):
System.out.println("Open the following URL and grant access to your account:");
System.out.print("Hit enter when it's done.[Enter]:");
String pin = br.readLine();
accessToken = twitter.getOAuthAccessToken(requestToken, pin);
So basically Twitter is returning a PIN to me after I have granted access - and this PIN needs to be passed to the call to get the auth token. This also means to use a different method than in the original example.