Butterfly Catching only took me three tries, once I discovered the trick.

Navigate via the minimap, not the main screen.

The camera in the Macalania woods hates you, and is responsible for most of the screwups. You can't tell where precisely you are on the trail, or where the butterflies are, since it is so zoomed back and at such a low angle. The minimap is much nicer to you (since it shows exactly where on the path you are), especially if you get a map of the butterfly locations to know exactly where to avoid.