Actually, while the Tor line is indeed a romance line, the Harlequin Luna line is NOT. They are a fantasy line. It's where the books are shelved. They only want around 25% of the plot to contain romance, and the female character should be the lead (female-centric). The Luna line also requires that it be a TRUE fantasy with world building. Urban fantasy (paranormal/fantasy elements inserted into our existing reality) need not apply.
What you'll need to decide when the book is done is whether you have a fantasy romance or a romantic fantasy.

Yeah, yeah, I know what's running through your mind right now---aren't they the same thing?
Nope.
When you say it's a "critical part" of the story, does the romance solve the primary plot? IS the romance the primary plot where the GOAL of the book is to get the people together into an HEA (Happily Ever After)? If not, then you've probably got a romantic fantasy on your hands and should probably look to to Roc, DAW, Kensington or some others to be placed in a fantasy line. If the romance doesn't exceed 25% of the plot and the female character is the lead, then look to Luna. But if it's a TRUE romance, where neither the fantastical elements NOR the romance can be removed and have the other remain, then you probably have a fantasy romance, which would work for a number of romance publishers like Tor, Warner, Berkley, Dorchester, etc.
Good luck!
