Illustrator is essential if you want to be professional. You can design with other things, but Illustrator will be demanded by so many clients that you'd be wasting your time as a designer if you didn't have it. You can get Illustrator CS2 and the rest of CS2 for free right now from Adobe's website. If you get good with it, and the situation demands it, you might consider getting CS6.
However, first of all you should establish that you're actually good at designing icons. I don't know anyone who just designs icons for a living, and if those people exist then they must be very rare. Logo design is commonly just one part of designing a corporate identity, which is a broader thing. You ought to be able to do this with pencil and paper, and often that's where logos begin before being scanned, reworked and vectorised. Compare your work with other people as much as possible: [link][link]
The only way is to study and study more. You can buy some books about the process in making a logo, that includes the brief, the color theory, the semantic and morfologic analysis as well the different types of typography. And then practice on paper and later on a vector program.
it's all about the idea and what the logo communicates, aswell as readability. you want it to read in all sizes, and in black&white. you also want them to be very unique and distinguishable. that's why high tier logos are kept rather simple and clear and don't overdo the use of color or symbolism. the execution of the final idea, which like some already said is almost always done in adobe illustrator (you want a vector file), is really just the very last 1% of the work. the 99% before that is purely mindwork and research.
this is not the best example but it should give you the right idea [link]
if you want to work in branding and corporate design (very fun field) you might want to look into studying viscom or graphic design.
It would actually be more important to learn graphic design theory and practices. You can design a good logo on paper. In truth when I design logos I rarely do all the work on computer, I design it by hand on grid paper and just trace it in.
I would like to suggest checking out Inkscape for graphic design. It's a fantastic vector graphics editor with many similarities to Adobe Illustrator. It's used by many professionals in art and game development as well, and it's currently my personal favorite graphics editor to use. Oh, and best of all, it's completely FREE and open source.
There is a bit of a learning curve, as is the case with many unfamiliar graphics editors, but it's definitely worth learning. Check out some YouTube videos regarding Inkscape to get a better understanding of what can be achieved by using this program and also search for tutorials as there are several helpful ones online.