When one says "Boruch Atta Hashem" in error he can say "Lamdeini Chukecha (לַמְּדֵנִי חֻקֶּיךָ)" and this way he did not say Hashem's name in vain since he has then said a complete verse (Psalms 119:12). Is there anything one can do if he said "Boruch Atta Hashem Elokeinu" in error other than saying "Boruch Shaim Kevod Malchuso Lolam Vaed"? (Source please.)
Say the verse (Deuteronomy 5:2):
יהוה אֱלֹהֵינוּ כָּרַת עִמָּנוּ בְּרִית בְּחֹרֵב
If you just said "Boruch Atta Hashem Elokei-" you can finish it with the end of the passuk (and you can say "baruch shem..." after that):
ברוך אתה ה' אלוהי ישראל אבינו, מעולם, ועד-עולם
If you already said Elokeinu, you may be stuck, since there's no passuk that has all those words together. I'm not sure if DoubleAA's suggestion would work since you used "ברוך אתה" as part of the phrase, so I think at that point you should just say "Boruch Shem".
Source Update: Kitzur Shulchan Aruch 6:4.