First to say: I don't know the climate in your area, but if Lemberger/Blaufrankisch does fit, then any other Variety that grows in Austria and Germany would also do (As Lemberger is one of the more demanding Austrian Varieties)!
Here are some examples:
vinifera, red:
Zweigelt: austrian variety, high yield (needs reduction), early ripening, easy to handle, good frost hardiness, uncomplicated taste, easily drinkable.
St. Laurent:Austrian variety, low yield, rather early ripening, very sensitive to late frosts and during flowering, very distinctive taste, and definitely a rare speciality!
Blauer Wildbacher: Austrian variety, low yield, very late ripening, difficult to grow, creates a very acidic rosé with a distinctive rasperry and redcurrant nose. Only suitable for red wine if harvested very late. Definitely a rarity!
hybrid, red:
Roesler
Rathay
Rondo
All three are early ripening, frost hardy varieties with high yields, and medium resistance to funghal diseases. They produce very dark and intensive red vines.
vinifera, white;
(Gewurz-)Traminer:
South-tyrolean variety, low yield, rather late ripening, sensitive during flowering, very intensive floral taste, very low acidity and excellent for dessert wines
(Gelber) Muskateller:
One of hundrets Muscat-subvarieties. late ripening, sensitive during flowering, difficult to grow. Very enjoyable floral taste, in Austria very popular as dry and sweet wine.
Scheurebe:
Quite new german variety. Late ripening, good frost hardiness. Good for desert wines.
Gruner Veltliner:
Most popular wine of Austria. Very wide variety of w inestyles. very high yields (needs reduction), sensitive during flowering, sensitive to chlorosis. Standard qualities are high in acidity and have a slightly peppery note.
hybrid, white:
Sorry, no (good) experiences so far
Of course there are many more varieties but I didn't taste all of them.
The "grapes" section of this site might also help you:
http://www.winemakingtalk.com/grapes/