I have launched a publication last year August 2012. So far I have 365 readers. Now I realised that the market is changing and also need to get along with the change. I also want to incorporate a wider spectrum of readers and advertisers as well.
I haven't had any advertisers so far purely because most advertisers are interested in reaching a certain market.
Changing the name of your publication can be done at any time. "Rebranding" as it's called can become very costly with a more widely distributed product, though. Because of this you may want to get your rebranding out of the way now.
What most companies do is notify their readership beforehand they will be changing names and/or focuses. If readers are aware of the coming changes they will be less likely to have a negative reaction, and more likely to stick with your publication. It's worth noting that this is also a chance for you to "sell" your publication - "new and improved" comes to mind.
You mentioned you want to increase the range of readers you have, but you also mentioned how the advertisers you have spoken to want to appeal to specific markets. Right now you should focus on what you want the future of your publication to be. Are you searching for a wide range audience ("Food Network Magazine") or a niche audience ("Gluten Free Celiacs Magazine")? Advertisers will pay more for hyper-targeted (niche) publications because they know it will net sales. But, if you want to increase you only want to increase exposure a wide range publication may be better.