This is essentially the same as issue
When 1102 was fixed in https://github.com/fcrepo/fcrepo/commit/2aa71e3db6f2aba5b66b22783594b035fbe0119d the VALID_PID_PART regular expression constant was added to FedoraObjectsResource and DatastreamResource, but the original (problematic) regular expression is still present in RelationshipResource.
Currently it uses ([A-Za-z0-9]|
))+ which matches "test:1234" but not "test:%3a1234" (see http://fiddle.re/pp0m ). The VALID_PID_PART regular expression correctly matches either PID.