This is definitely fixed in the 2.1.x branch but is still a problem in the 2.0.x branch (just tested in 2.0.10). If you create a post dated for some time in the future in a category that contains no other posts and then publish it, a category link is instantly created by wp_list_categories() but clicking that link generates a 404 error.
I'm trying to avoid being needlessly verbose, but if that is too terse please ask me for more details.