Is it possible to change ENUM() lists? I wasn't sure if changing ENUM() list isn't possible so I made a test.
In MySQL v5.1.58 I made a test InnoDB table that contains one field called 'bool' of type ENUM('yes', 'no').

Then I executed...

ALTER TABLE  `test`
CHANGE  `bool`  `bool` ENUM(  'yes',  'no',  'maybe' )
CHARACTER SET latin1 COLLATE latin1_swedish_ci NOT NULL


...and it worked.

Have I done anything wrong? Is it dependent on db engine?Why everybody says changing a ENUM() list isn't possible? eg. here http://komlenic.com/244/8-reasons-why-mysqls-enum-data-type-is-evil/
As long as the table is empty, there is no problem. As long as new values for ENUM is appended and not renamed given a populated table, again no problem.

The ENUM you redefined in your question actually kept the original internal values for yes and no as the test table last remembered it. 

The following applies to populated tables:

What about this?

ALTER TABLE  `test`
CHANGE  `bool`  `bool` ENUM(  'no',  'yes',  'maybe' )
CHARACTER SET latin1 COLLATE latin1_swedish_ci NOT NULL


Now you have a problem. The ENUM values in a fully populated table would have their internal values reversed so that yes is now no and no is now yes.

What about this?

ALTER TABLE  `test`
CHANGE  `bool`  `bool` ENUM(  'maybe', 'no',  'yes' )
CHARACTER SET latin1 COLLATE latin1_swedish_ci NOT NULL


Big Problem. In a populated table, yes is now maybe. New rows inserted with yes are disconnected from the previous yes rows because they now mean maybe.

SUMMARY

There are very high-risk, bait-and-switch techniques to do this very quickly in MyISAM. I would strongly advise against doing this in InnoDB because of its tablespace id interaction with ibdata1.