mysql - creating index takes too much time?

I have an InnoDB table, with lots of fields, and currently 0.7M rows. Now, I created 3 enum columns and created an index on them (the current value in the column is null). On each of the columns, creating the index took approx 11 minutes. Is this expected?

I am finding that queries on the table are taking too much time also. Queries like selecting few columns from all rows with one field (timestamp) value within certain range, takes 2-3 minutes.

The table has approx 20 fields, many of them are varchar(255), some of them TEXT, some integers, etc.

The machine (a VPS) has 512MB ram and 1Ghz cpu

Basically I want to know whether these times are unexpectedly long, and if so, then is it due to my machine or table design.

Are you using MySQL 5.1 with the InnoDb plugin? That has the fast index create functionality.