Ich bin der Meinung, man sagt in gutem Deutsch "frisch vermählt". Als Nachweis kann ich hier höchstens die Google-Hits für beide Varianten anführen: 177 für neu vermählt und 711 für frisch vermählt. Der Duden sagt übrigens:
neu|ver|mählt (gerade, eben erst vermählt), aber neu ver|mählt (wieder, erneut vermählt)
© Duden - Die deutsche Rechtschreibung, 23. Aufl. Mannheim 2004 [CD-ROM]
"Newly-married könnte demnach nur eines von beiden sein, also entweder "neu vermählt" oder "neuvermählt" (sprich: "neu vermählt" wäre sogar nicht nur nicht schön, sondern falsch!). Zu "neuvermählt" ist noch anzumerken, dass es zwar im Duden steht und existiert, schaut man sich aber die ersten Google-Hits an, so sind das alles Wörterbücher. Das spricht immer dafür, dass das Wort eher im Sprachgebrauch selten ist.
In den zusammengesetzten Einträgen kommt newly-married als "frisch verheiratet" schon vor. Und wo ist eigentlich das so bekannte "just married"? Ich hoffe ich habe jetzt nicht allzusehr verwirrt :-)

konkret:
newly-married = neu vermählt raus, stattdessen newly-married = frisch vermählt rein
evtl. frisch verheiratet ebenfalls als Übersetzung dazu
evtl. eine andere englische Übersetzung für "neu vermählt".