I've checked out Presta... the interface isn't very clean. It needs a lot of work. It is like someone started with a basic cart and decided to add all these extra features without any planning.
I have also looked at Magento. It is a great cart. The only problem is that the Community Edition (professional starts at $3k+ a year, enterprise $12k+ a year) is missing most of the features. Some very basic ones that are necessary for any modern online store.
I haven't done anything with Zen Cart, but will take a closer look.