I cleaned and gutted a whole fish then stuffed with rosemary and garlic. Wrapped it foil and cooked it on charcoal grill. After it was done cooking, the fish lacked the flavor of the herbs.
How much rosemary and garlic did you stuff into the fish? A sprig of rosemary and a clove of garlic in a 4 lb fish isn't going to do much, but too much would overpower the fish.
I personally like making a rub for the outside of the fish of whatever I am stuffing it with. In this case, take a few rosemary leaves and a few cloves of garlic and make a light paste , then rub it on the outside of the fish. Then, stuff the fish with rosemary sprigs and garlic cloves (sliced or mashed if possible to extract more flavor). Whenever I stuff a fish, I also tend to add 1 tablespoon of butter and spread it on the inside of the fish to act as a conduit for the flavor.