I have now tried myself and can confirm this problem in both directions (phone to pc and pc to phone). hcid says something like
Passkey agent replied with an error: org.freedesktop.DBus.Error.UnknownMethod, Method "Request" with signature "ss" on interface "org.bluez.PasskeyAgent" doesn't exist
and passkey-agent gives the same error as you described. This is on a debian lenny/sid. This has worked all right some weeks ago, so it must have come in with an update.
Maybe someone else has information on the issue ...