When you click on the "Rebuild Last" link in the main menu, it will trigger the build which was the last one when the page was loaded. If there have been other builds in the mean time, they will be skipped.

This is especially annoying for parameterized jobs, of course.

The reason for this is because the link contains the fixed build number in its URL, eg. ../jenkins/job/my-job/6139/rebuild. A simple solution would be to simply use lastCompletedBuild instead of the build number in the link. It will then always use the last build that is not currently running.