Sorry to hear about the difficulty mining up catalyst, Haha. That's no fun.

If you're looking for where to mine/log/fish for certain materials, I'd suggest checking out Mooglebox.com. They've got a gathering index that shows the camps, rank, sweet spot, remainder bar, strike location, and yield for ... well, as far as I can tell, every item in the game. It's enormously helpful if you're trying to figure out where to gather specific items.

Different camps offer different types of materia. And you have to use different gathering jobs to get catalysts in different regions. For example, in order to get catalysts from Camp Bloodshore or Camp Cedarwood in the LL region, you have to fish for the catalyst. In order to get catalysts from Camp Iron Lake, you have to use botany to gather the catalysts. You won't be able to get any catalysts by mining near those camps.

If you want to mine for catalysts, you'll have to go to Horizon (near Uldah), Nophica's Wells (near Uldah), Dragonhead (in Coerthas), or Treespeak (near Gridania).

You'll be able to trigger the ability as soon as you learn and equip it. Having raised you mining level that high, I'm sure you already know that you get more attempts on lower level mining nodes, and fewer attempts on higher level mining nodes. You'll also be less likely to successfully mine at higher level nodes. Other than that, your level shouldn't matter when gathering catalysts. For now, if you stick to mining Carbonized Matter at Horizon (Level 8), and Petrified Matter at Nophica (Level 28), you should be fine. You may want to wait a few more levels before mining Fossilized Matter at Dragonhead (Level 38), and Crystallized Matter at Treespeak (Level 43).

Please note that the sweet spot for all fishing catalysts is -5, meaning you move the strike bar all the way down to the bottom of the bar. The sweet spot for all mining and logging catalysts is +5, meaning you have to move the strike bar all the way to the top of the bar. Putting the bar on the sweet spot won't guarantee that you get that item, but it will increase the chances that you'll get it.

Congratulations on raising your mining level high enough that you're starting to look for catalysts. Hope that helps you find what you're looking for, so you can start melding some sweet, sweet gear.