One way of handling this was through providing the requirements to them earlier than the above process. We work with several external teams, such as the team that works on our installer and release process, and teams that provide us components (with the same components being provided to other teams as well). We typically would have a lot of work for our installer / release teams, and hence it was difficult for them to do a lot of new work during the operative parts of the cycle where feature work was doing (getting a stable build and release process, and ensuring that defects were fixed, that glitches in the process were repaired, that builds that were broken were repaired and the process modified to ensure that the builds did not break again for this reason); hence we had to take a new strategy for getting new work done.
What was this strategy. We took the list of features that were proposed for the next couple of releases, and did a sorting of features where there was some changes required from the installer / release teams or from the teams that prepared the installers. Once this done and we had a list, we would run the list again with the product manager and do a prioritization of the features. At the same time, we also had discussions with the external teams on the amount of work that they could do and what was feasible for them (for example, there could be resource constraints or the organization priority for a product could be higher than the priority of your product), and also generated some estimates from them. This was an iterative process, since if a high priority feature required a lot of work from the external teams that they were unwilling or unable to provide, we would have to jiggle the list around to either modify the feature so that it was still feasible, or drop it entirely (and this not easy - once we dropped a feature that was #3 on our top list, but it required support from an external team to a resource level that they were unwilling to commit and for which even escalation did not help). This took some weeks, but at the end of this, we had a list that we could provide to our external teams.
Now all this is not useful unless it is done early in the cycle, and that is what we did. We took the list of features generated from the process that is described above in the middle of the current cycle and talked to our external teams so that they could accommodate this in their cycle; and in most cases, the extra available time was just the buffer required to ensure that the work could be done by the external team and be available in time for when the next version of the product started and work was being done on those features in the core development team. Of course, in some cases, even this extra time will not work if the team is not getting the sufficient priority by the external team, and sometimes you just have to shrug and accept it (after you have done all the escalation and prioritization discussions).