I also have this problem, which is there in 1.389, but was not in 1.384. Here's my description (as sent to the mailing list):
If you use build triggers with tokens, be aware there is an issue in 1.389.
I click the "build" icon, and get taken to a web page that says "Access Denied. Invalid token provided.". The console log for Hudson shows:
[webapp 2010/12/16 12:33:34] - While serving http://<hudson-master>:8080/job/<jobname>/build: org.acegisecurity.AccessDeniedException: Invalid token provided.
This happens for some jobs and not others. According to the job permissions, I should be able to start the build, and this worked in prior versions. The factor in common for the jobs that say "Invalid token provided" is that they all have the "Trigger builds remotely (e.g., from scripts)" build trigger configured (sometimes they have other build triggers also), with a token specified.