The Tal Shiar operatives held captive by the Dominion were willing to work with Cardassians and Federation prisoners to escape, and one sacrificed his life to save the others. Also the Romulans in "The Chase" were the most open-minded ones of the lot of aliens chasing the Precursors' secret (aside from the Feds), and the Romulan Captain from "Face of the Enemy" was pretty non-hostile as well.
I'd say there is plenty of evidence showing that they could work with a crew of Feds in the name of survival, while their differences would also make the show more interesting. It would be a "We may have both been wrong about the other" situation.
Plus, if there's 120 Feds and 30 Romulans, they'd think twice about trying to kill them all and steal the ship. And you could just have the Fleeters pull a sacrifice in the premiere that makes them think "Okay, they DID sacrifice to save us, so let's not immediately try anything."
You didn't even have to say all of that.
"Message in a Bottle"
"Romulans"
"Prometheus"
You get the point?
Nuff said.
