I am reminded of the famous Intel Pentium FDIV bug (1994). Seems they had implemented a new and improved floating point division algorithm. It needed only half the cycles of the previous algorithm.
The new algorithm used a 1066-cell lookup table to find partial quotients used in the calculation. Unfortunately, due to a screwup, five of the cells were left blank when the ROM was loaded. This led to obscure errors in the results, which went unnoticed until many thousands of chips were in customers' hands. At that point, Intel had a massively embarrassing recall on their hands.
Example: (core i7, may 2011) http://download.intel.com/design/processor/specupdt/320836.p...
BIOS updates often contain bugfixes for your CPU.
[1] http://lists.debian.org/debian-user/2012/11/msg00193.html
Microcode in its most basic form is just a big look-up table (could be nested if word size is limited) containing the electrical signals for a particular instruction, and a new address to "jump" to (either a subsequent micro-operation, or jump back to the "fetch" micro-op). Electrically, however, there's no difference between a microcoded and hard-wired CPU - they both fetch and execute sequences of instructions.
Of course, there's an obvious advantage to the microcoded approach: your instruction set gets uploaded to your hardware in a ROM! You can change the operation of instructions after the hardware is made, make custom sequences of instructions, or even fix microcode bugs (while uncommon, there have been cases in the past).