Karen,
I've never used the traditional Red Velvet Frosting before, but have had great success using a basic cream cheese frosting which not only goes great with it, but I always get great reviews. I use the same frosting that I put on my carrot cakes. Here it is:
Cream Cheese Frosting

1 pound powdered sugar sifted, 8 ounces softened cream cheese
1/4 cup softened butter or marg. 2 tsp. vanilla (clear if possible, if not don't worry!)
mix all ingredients until smooth. Store cake in fridge. Enjoy

Good Luck!
SC