Ok- i have never made fondant, but i've heard a lot about marshmallow fondant. There is a simple recipe on here.
http://www.cakecentral.com/cake_recipe-1949-2-Marshmallow-Fondant-MMF.html
I know that marshmallows are made of gelatin, but a vegan friend of mine always has these on hand:
http://www.veganstore.com/850.html
since i don't know much about the chemistry of marshmallows or fondant or anything, i couldnt really tell you how it would turn out, but it sounds like it might be worth a try!
good luck! 
Here is a recipe I was just glancing at today:
Noi's Chocolate Fondant
1. 12 oz. Vanilla flavor Merckens white summer coating
2. ¼ cup Light Karo syrup
3. 2 lbs. Powdered sugar (can be sifted)
4. 2 tsp. Tylose or CMC
5. ½ cup Shortening (Crisco melted)
6. ½ cup Light Karo syrup (do not substitute)
7. 2 tsp. Glycerin
8. 2 tsp. Flavoring (Crème Bouquet, Lemon Oil, etc.)
9. 2 tsp. **Agar-Agar** powdered ( found in oriental or health food stores. See note **)
10. 3-4 TBSP Hot water
Melt summer coating as direction on package; add ¼ cup Karo syrup. Stir
until mix together. Set aside to cool. This is basic candy clay recipe.
*** One recipe of candy clay will make 2 batches of this fondant recipe ***
Place powdered sugar and Tylose in KitchenAid mixing bowl (or any stand
mixer), make a well in center.
Melt Crisco in microwave on high about 45-60 seconds.
Add items number 6, 7, and 8 to melted shortening, stir to combine.
Dissolve Agar-Agar powdered in hot water.
Pour shortening mixture and dissolved Agar-agar in center of mixing bowl.
Attach dough hook and mix on low until mixture gets soft. Add half of candy
clay to the dough and mix about 30 seconds more.
Place dough on counter top; knead by hands until soft and pliable. Cover and
let set over night.
**NOTE: Gelatin is made from animal by-products. Agar-Agar powdered is made from plant**
If you cannot find Agar-Agar, use the Buttercream/Fondant recipe from Carol Webb of Elegant Lace.
Any questions please contact me.
It came from this site: http://sugarcraft.com/catalog/misc/homemadechoco-pan.htm
Here is the buttercream fondant recipe mentioned above:
http://www.thehoustoncakeclub.com/goodfood/bcfondant.htm
Whoops! after closer inspection I see this has gelatin. Hmmm....strange reference. Oh, well. Perhaps you'll have some luck finding that agar-agar stuff.
thanks alana! This is really a great topic, and i think next month i'll try that for my friend's birthday cake! (i'm sure it'll turn out better than experimenting with those marshmallows!)
Gee, I just love this place! I'm getting answers to questions I didn't even know I had! What a wonderful community 
I have a friend that is a vegan and she does the fondant out of marshmellow fluff and podered sugar. I know that the recipe is here somewhere. It is very simple. I know that there have been talks about it being ideal for vegans and others and people are happy with the way that it turns out. I tried useing it myself and it was just fine. Here is the recipe, I got it here on CC. Hope this helps.
Vicky
This is not my recipe, it was place by another CCer.
_____________________________________________________________
Easy Marshmallow Fondant
Serves/Yields: enough to cover 10" cake and decorations
Prep. Time: 2 minutes
Cook Time:
Category: Amish/Mennonite
Difficulty: Easy
An easier way to make marshmallow fondant which doesn't require the use of the microwave
1 16oz tub of Marshmallow fluff
6-8 cups of confectioners sugar
2 tsp of flavoring of your choice
paste colors (Optional)
Empty contents of marshmallow fluff in large bowl. add flavoring and stir with spoon. If you desire to color the fondat add your desired color at this stage. Then add confectioners sugar two cups at a time and mix with spoon until no longer sticky, then place on large pastry board or mat lightly rubbed with vegetable shortening and knead until smooth and pliable. Roll out to desired size for covering cake.
Note: The finished fondant is bright white in color due to the marshmallow fluff, which is whiter than marshmallows
To Store: wrap in plastic wrap then place in zip loc bag
Nutrition Information
0 grams of fat
40 calories per serving
Source: Nesmar
Contributed by: nesmar on Thursday, March 30. 2006 at 06:27:07
Quote by @%username% on %date%
%body%