I've made my first logo in Fireworks) and it looks ok at full size but when scaled down it looks pretty bad. Is it common for designers to make separate versions for smaller sizes?
It's true that a logo must look as good on a billboard as it does on a business card. That doesn't mean the same artwork will work in both cases.
It's not uncommon for the full-scale version of a logo to have detail that becomes completely lost or too fine and "busy" when scaled down. Stripes, strokes, even a typeface must be adjusted for tiny applications. Among other practical considerations is the fact that fine details that look great at larger sizes can bleed or disappear entirely on press, yet would look too heavy if scaled to compensate in the larger version. (This is the same reason we have optical sizes in modern professional fonts. What works for a tiny caption looks far too heavy if used in a 72 point headline.)
John McWade has an excellent example of this problem, and its solution, in his book "Before and After Graphics for Business." His demonstration logo, with 19 nicely geometric lines at full size, has to change to 5 lines in the small-scale version to maintain the look of the original.
I create small and large versions of logo designs when the design requires it, a common case being to switch from a light font in the "large sizes" version to a book or regular in the "business card" version (and often, in such a case, the web version). The important thing is that the optical appearance is the same, and that depends on more than just the mechanics of a piece of artwork. As with so many design details, it's the eye, not the ruler, that dictates the final result.
So... to answer the question: if your logo doesn't work when it's tiny, reduce the fine detail (or make strokes a little thicker) until you get something that has the "look" of the original. You may have to go back and forth between the two until you have a combination that works, and it may be that your big, bad logo is way too busy, no matter how spiffy it seemed when you first came up with it. Sometimes the delete key is your best friend.
It's important not to over-complicate logos.
I believe it's more typical to design logos to be well suited for a broad range of sizes, as well as making it look good in both color AND black and white. When designing a logo you can't be 100% certain exactly what for the logo will be used for, so it needs to be as versatile as possible.