What I did was download WordPress version 2.6.5 and ftp'd two files from it up to my WordPress 2.7 installation. The two files were:
wp-cron.php and cron.php
wp-cron.php resides in the root WordPress installation and cron.php resides in the wp-includes folder and basically uploading both of these files overwrote the WP 2.7 versions of these files and everything worked.
In wp-cron.php there is a line about "local time" in the coding and I suspect that if your web server is not exactly correct in the local time from what WordPress perceives it to be, then the timeout of zero to do the cron job will effectively cancel the trigger of the scheduled post.
These two files in WordPress 2.6.5 do not have the "local time" variable in the code as well they have a trigger time of +30 and this fix really does work for about 97% of the folks who have tried it so far.
Since it's not working for you, double-check that you uploaded both of these files to the right folders, double-check that you can overwrite these files and your server does not have them write-protected somewhow, make sure you're not running on a Windows 2003 server or you will have to do an iisreset in order for the cron jobs to trigger in wp-cron.php and cron.php
If all this still doesn't get you up and running then have a look at some other variables like are you able to run a backup of your website? Any other cron jobs? Do they work or not? Perhaps it's an issue at your server level and not in WordPress?
One thing I did before I tried this fix that I came up with is I set up a sub-domain on my hosting account and loaded in WordPress version 2.6 and tested a scheduled post, it worked like a charm. Then I loaded in WordPress 2.7 and scheduled a post, it failed saying "Missed Schedule" so I satisified myself that the problem was definitely not with my server but with WordPress 2.7 - Overwriting those two files did the trick for me and quite a few others now...
Sorry it isn't working for you...I hope they resolve this in the next version of WordPress...