I would argue that publicity itself doesn't help. the program needs to be useful to people, if it's useful word gets around. you do need some publicity, but it's not expensive campaigns.
the real cost of growing a community is dealing with the 'whiners' when the community is small, bringing the new contributers up to speed, working with them to change their patches into something that's acceptable for the project, taking the 'works but is not quite right' patches and assigning someone to clean them up, writing documentation, etc.
when the community is small, these things will distract your paid people, but they are needed to grow the community. it's a long-term investment, and it doesn't always pay off, but when it does it can pay off in a big way.