Nick; I posted a macaroni salad on my blog that uses Vegenaise and have a potato salad on there somewhere too, just search (my connection's too slow right now...).
Tofu-NOT-Egg salad is so easy too.
Mash some firm tofu with V'gnaise, add a couple Tbsp. VERY finely chopped onion, sweet-pickle, celery.
Mix with V'gnaise to the consistency of egg salad.
Season to taste with celery salt, a couple drops of vinegar, some yellow mustard, and pepper. (If you have it, some India Black Salt adds an eggy flavor that will totally fool most egg-eaters!)
... My gosh though, any recipe traditionally calling for mayonnaise would work: potato salad, macaroni salad, sandwiches, burgers, "ranch" dip, dressings, coleslaw, ... just google "potato salad" or whatever you want...