The cause of this is floating point calculation. It's rounded.
Possible patch is

diff --git a/ext/standard/basic_functions.c b/ext/standard/basic_functions.c
index 2b70414..44a41e4 100644
--- a/ext/standard/basic_functions.c
+++ b/ext/standard/basic_functions.c
@@ -4486,8 +4486,8 @@ PHP_FUNCTION(time_sleep_until)
        if (php_req.tv_sec > c_ts) { /* rounding up occurred */
                php_req.tv_sec--;
        }
-       /* 1sec = 1000000000 nanoseconds */
-       php_req.tv_nsec = (long) ((c_ts - php_req.tv_sec) * 1000000000.00);
+       /* 1sec = 1000000000 nanoseconds. Add 0.5 sec round margin */
+       php_req.tv_nsec = (long) ((c_ts - php_req.tv_sec) * 1000000000.00 + 0.5) ;
 
        while (nanosleep(&php_req, &php_rem)) {
                if (errno == EINTR) {

Oops. Round margin should be something like 0.99. Or use ceil() to be precise.

My previous analysis is wrong.
time_sleep_until() sleeps as it supposed. It seems date() is doing something wrong.

You can see it's sleeping as it supposed by replacing date() to microtime()
<?php
$sleep_until = microtime(true) + 1;
echo "sleep until " . $sleep_until ."\n";
time_sleep_until($sleep_until);
echo "woke up at " . microtime(true);
?>

By the way, the code works fine on Windows: time() - $sleep_until = 0 consistently. Tried the same code on Ubuntu 14.04 and would get -1 consistently.

Yes, date() seems to have a bug:
<?php
function udate($format, $timestamp=null) {
	if (!isset($timestamp)) $timestamp = microtime();
	// microtime(true)
	if (count($t = explode(" ", $timestamp)) == 1) {
		list($timestamp, $usec) = explode(".", $timestamp);
		$usec = "." . $usec;
	}
	// microtime() is more precise
	else {
		$usec = $t[0];
		$timestamp = $t[1];
	}
	// 7 decimal places for "u" is maximum
	$usec = substr(sprintf('%.7f', $usec), 1);
	$date = new DateTime(date('Y-m-d H:i:s' . $usec, $timestamp));
	return $date->format($format);
}
echo "### first test ###\n";
$sleep_until = round(microtime(true)) + 3.002;
echo "sleep: " . udate("Y-m-d\TH:i:s.u", $sleep_until) . "\n";
time_sleep_until($sleep_until);
echo "udate: " . udate("Y-m-d\TH:i:s.u", microtime(true)) . "\n";
echo "date : " . date("Y-m-d\TH:i:s") . "\n";
echo "### second test ###\n";
$sleep_until = round(microtime(true)) + 3.003;
echo "sleep: " . udate("Y-m-d\TH:i:s.u", $sleep_until) . "\n";
time_sleep_until($sleep_until);
echo "udate: " . udate("Y-m-d\TH:i:s.u", microtime(true)) . "\n";
echo "date : " . date("Y-m-d\TH:i:s") . "\n";
/* results:
### first test ###
sleep: 2015-02-14T14:29:51.002000
udate: 2015-02-14T14:29:51.002100
date : 2015-02-14T14:29:50
### second test ###
sleep: 2015-02-14T14:29:54.003000
udate: 2015-02-14T14:29:54.003100
date : 2015-02-14T14:29:54
*/
?>

Here is the reason for the discrepancy: https://stackoverflow.com/questions/22917318/time-and-gettimeofday-return-different-seconds

TLDR We use two different APIs for time() and microtime() and the latter is not just more precise when it comes to sub-second resolution, it also calculates the seconds more precisely.

The fix for this bug has been committed.

Snapshots of the sources are packaged every three hours; this change
will be in the next snapshot. You can grab the snapshot at
http://snaps.php.net/.

 For Windows:

http://windows.php.net/snapshots/
 
Thank you for the report, and for helping us make PHP better.

The behaviour of the following code has changed with this fix. It used to  produce different timestamps for the two test files. With the fix for this bug, the timestamps are always the same, which is kind of unexpected. 

We have worked around this (or implemented this properly, depending on how one sees this) by waiting for fstat($f)['mtime'] on a freshly modified file to change, instead of waiting for time() to change.

<?php

$f = tmpfile();
$start = time();
print('old time: '.fstat($f)['mtime']. "\n");
fclose($f);

/* wait for the next second */
do { } while ($start == time());

$f = tmpfile();
$start = time();
print('new time: '.fstat($f)['mtime']. "\n");
fclose($f);