Sorry, it should be:

class F extends D
{
    private function test() { } // stiffen visibility from public to private 
(unexpected)
}

But nevertheless.

I reported this same problem a few years ago here: https://bugs.php.net/bug.php?id=48376
I was told this was not a bug (although I haven't a clue as to why its not deemed as such).  I believe C# allows you the ability to do this as it would resolve up the scope, but as of 5.4.0 I still cannot get why it allows forced reduced scopes during declaration, but provides an uncatchable fatal error on call.
I'm still most concerned by the allowed reduction from an interface.  There is no way to guarantee that an interface will implement the method in question regardless of if it is known to be that type which truly is a shame.

If you'd stiffen visibility you'd be violating the is-a contract given. If an object is using a classed derived from A and I can do "instanceof A" I expect to be able to call all methods from A and having them do something like A's method does. When stiffening that won't be the case anymore.

Johannes, I think you are actually agreeing with him here. As per Liskov you 
can't tighten visibility, you can only loosen it on inheritance. However, in this 
case you aren't tightening it because the original was private, so setting it 
back to private is allowed and doesn't violate Liskov.

You guys have me a bit confused now.  You seem to be in agreement that an inherited method cannot decay the scope of the parent's method (since PHP doesn't bubble up), yet you are indicating that this isn't a bug.

I'm still curious on how to get around the interfacing issue.  For an example:

Test Script:
---------------
<?php

interface IInterface
{
	public function test();
}

class Grandfather
{
	private function test()
	{
		return __METHOD__;
	}
}

class Father extends Grandfather implements IInterface
{
	public function test()
	{
		return __METHOD__;
	}
}

class Son extends Father
{
	protected function test()
	{
		return __METHOD__;
	}
}


function printTest(IInterface $i)
{
	return $i->test();
}

$aObjs = array(new Father(), new Son());

$rcInterface = new ReflectionClass('IInterface');

foreach ($aObjs AS $obj)
{
	$rc = new ReflectionClass($obj);
	$testMethod = $rc->getMethod('test');
	printf('%s' . PHP_EOL,
		str_pad($rc->getName() . ' START', 25, '-', STR_PAD_BOTH));

	// Procedural checks
	printf('%s instanceof IInterface? %d' . PHP_EOL,
		$rc->getName(),
		($obj instanceof IInterface));
	printf('is_a(%s, IInterface)? %d' . PHP_EOL, 
		$rc->getName(),
		is_a($obj, 'IInterface'));
	printf('is_subclass_of(%s, IInterface)? %d' . PHP_EOL, 
		$rc->getName(), 
		is_subclass_of($obj, 'IInterface'));

	// reflection checks.
	printf('(Reflection)%s::implementsInterface(IInterface)? %d' . PHP_EOL,
		$rc->getName(),
		$rc->implementsInterface('IInterface'));
	printf('(Reflection)%s::getInterfaceNames(): %s' . PHP_EOL,
		$rc->getName(),
		implode(', ', $rc->getInterfaceNames()));
	printf('%s::isInstance(%s)? %d' . PHP_EOL, 
		$rcInterface->getName(), 
		$rc->getName(), 
		$rcInterface->isInstance($obj));
	print('Methods:' . PHP_EOL);
	foreach ($rc->getMethods() AS $method)
	{
		$objMethod = $rc->getMethod($method->getName());
		try
		{
			$prototype = $method->getPrototype()->getDeclaringClass();
		}
		catch (ReflectionException $ex)
		{
			$prototype = $method->getDeclaringClass();
		}
		printf("\t%s prototyped by %s is public? %d" . PHP_EOL,
			$method->getName(),
			$prototype->getName(),
			$objMethod->isPublic());
	}

	printf('Call %s::test() via printTest: %s' . PHP_EOL,
		$rc->getName(),
		printTest($obj));

	printf('%s' . PHP_EOL, 
		str_pad($rc->getName() . ' END', 25, '-', STR_PAD_BOTH));
	print(PHP_EOL);
}

?>

Expected Results:
------------------
Fatal error: Access level to Son::test() must be public (as in class Father)

Actual Results:
------------------
------Father START-------
Father instanceof IInterface? 1
is_a(Father, IInterface)? 1
is_subclass_of(Father, IInterface)? 1
(Reflection)Father::implementsInterface(IInterface)? 1
(Reflection)Father::getInterfaceNames(): IInterface
IInterface::isInstance(Father)? 1
Methods:
	test prototyped by IInterface is public? 1
Call Father::test() via printTest: Father::test
-------Father END--------

--------Son START--------
Son instanceof IInterface? 1
is_a(Son, IInterface)? 1
is_subclass_of(Son, IInterface)? 1
(Reflection)Son::implementsInterface(IInterface)? 1
(Reflection)Son::getInterfaceNames(): IInterface
IInterface::isInstance(Son)? 1
Methods:
	test prototyped by IInterface is public? 0

Fatal error: Call to protected method Son::test() from context ''



So everything here does indicate that Son is a typeof IInterface, yet it clearly shows that the prototyped IInterface::test() has been demoted to a non-public scope.

The only way I can "fix" this is by double checking any check against the object in question:
function printTest(IInterface $i)
{
	$sResult = '';
	$rc = new ReflectionClass($i);
	$method = $rc->getMethod('test');
	if ($method->isPublic())
	{
		$sResult = $method->invoke();
	}
	return $sResult;
}

Which given the pass for the IInterface check on the typehint should contract that object to guarantee the IInterface::test method, yet here we must double check that its within an accessible scope and therefore violates the interface contract.
So I need to ask again, what is the purpose of the interface if the class isn't obligated to implement all the methods in a public scope?

I agree with kev here. LSP applies at all hierarchy levels. If the parent is protected, you can't go private.

C is a subtype of B, but you couldn't use it interchangeably due to different visibility. So LSP is clearly broken here.