Random audits from trusted third-parties would be a nice thing. Allow people to come in at any time and check the systems. Trust is better when distributed over multiple neutral parties.
In terms of features, allow clients to regularly change IP and don't log who is using what IP. Also mix client traffic with Tor exit nodes to add noise to the traffic.
I feel like people who complain about this are people who wouldn't be satisfied with anything unless they rolled it themselves. Of course, you could purchase your own server, use OpenVPN, etc. But anything that you haven't touched yourself is just one more thing that's potentially malicious.
What would it take to convince you that a VPN service was trustworthy?