For the last few months I've been helping large organization with their efforts to cross-certify their PKI infrastructure with Federal Bridge Certification Authority (FBCA). We had some technical challenges with interoperability between our systems which we were able to resolve fairly quickly with some help from product group guys and our own tireless testing. But at the end of the day the technical issues are really not that difficult comparing to the implementation of all required operational processes and ensuring that they are auditable by Audit Company. FBCA wants to know that cross-certifying agency is in full compliance with their Certificate Practice Statement (CPS). Auditors are the folks who actually provide report to FBCA about this compliance, and let me tell you, they do want to see working process (ie documentation, equipment, facilities, personnel etc) for every statement in your CPS. If you say in CPS that something is done certain way, well you better have actual process established, people trained etc on how to do that. Otherwise you'll fail the Audit and eventually might have problems with FBCA giving you a green light for issuing cross certificate keys.
In large organizations with multiple data centers, multiple departments, different contracting companies it can be fairly difficult to implement in short amount of time.