To add materia to an item, you must make sure, as you said, you have the appropriate quest finished, and a proper crafting Class. For example, if you don't have Blacksmith leveled, you can't meld materia to metal weapons, etc. Since you said you have both of those, doing it yourself is as simple as having the proper materia and the proper item. Then you right click on the item you want to meld to, and there should be the option "Meld." This will pull up a window where you select what materia you want to meld on, and from there, a window confirming what you're adding on.

Now that being said, I know they changed the job quests slightly, especially with not needing Carbonized Matter for non-quest melds but still needing the Grade 1 Carbonized for the crafting quests, so I don't know if perhaps that's changed. If that's not working, try this: with the later quests, they've added a new tab for DoH quests, maybe check there? In your crafting log, you'll see two buttons, one that is your "leveling" recipes and one that is your "special" recipes. Under special recipes, you might have one for jobs, and because of the changes with only job quests requiring the carbonized matter, there may be a recipe there or something similar. Worth checking, I guess? I already have all crafts at 60+ so I can't really go back to confirm myself post-change. =x

*grumbles at needing to edit to get more than 1000 characters for an explanatory post*