iOS Swipe to edit difficult to discover

A while back, we worked with a Ux/Graphics designer that was enamored with the (then) emerging "swipe to edit" trend for iOS apps. We ended up with something that looks like this on a swipe:

(nevermind the inconsistent color on the action icons)

Basically, a list view of stuff. And the user can swipe from right to left, which reveals the actions they can do on that item.

The flow works really nicely. BUT, users (many of ours are non-techie types) don't seem to discover this. Tapping and panning they get, but not these more specific gestures. They don't even seem to discover them, and when they do, they're surprised. I would say that despite iOS's support for the paradigm, it's not near as obvious to invoke yet.

I'm left at a fork in the road about which way to go from here: 1) Overcome the lack of discoverability with some help. Do a pop up the first time they come to the screen that informs them that there's this "hidden" feature they can use. 2) Somehow annotate the rows on the right (small left facing chevron?) hinting that swiping that way might lead to something. 3) Abandon the swipe as an edit action entry point, and do something else to make these row specific actions available and more discoverable.

Are other apps experiencing this same problem? How do they get around it? And what about Android (which we're beginning a port to right now).

(I think I've seen some apps that enable this model, but don't depend on it as the sole way of doing the actions, providing an alternate method somehow).