If you receive this message from Disk Utility after replugging an external drive that wasn't successfully ejected (or unmounted), it could be that the OS is already busy performing the repair in the background. Your Mac will not be able to mount the disk until after the automatic checks are complete.
If the external drive's activity indicator is blinking, but you are otherwise unable to access the drive, then some background process is working on your disk. To see whether this is the case, you can run the "process status" command in a Console shell:
[code]
Macbook-Pro: ~ luthien$ sudo ps ax | grep hfs
605 ?? R 4:08.59 /System/Library/Filesystems/hfs.fs/Contents/Resources/./fsck_hfs -y /dev/disk4s4
[/code]
In my case, my external drive (which I use for Time Machine backups) was given the name "/dev/disk4s4", and indeed the filesystem check program (fsck_hfs) command was still running. I let it do it's thing for a few hours; when it was done, the disk was automatically remounted and could be browsed in Finder.