What fruit pair well with spinach?
You might consider citrus or other tart fruit with citrus -- mandarin oranges segments are fairly common to pair with spinich; even if you didn't use whole fruit, consider making a vinagrette using orange juice.

I've also seen recipes for spinich salads with strawberries or cranberries;  I've also had a pineappe and avocado salad before that might work well with spinish instead of romaine.