optimization - How do I add indices to MySQL tables?

I've got a very large MySQL table with about 150,000 rows
of data. Currently, when I try and
run

SELECT * FROM table WHERE id =
            '1';

the code runs
fine as the ID field is the primary index.

However, for a recent
development in the project, I have to search the database by another field. For
example:

SELECT * FROM table WHERE
            product_id = '1';

This
field was not previously indexed; however, I've added one, so mysql now indexes the
field, but when I try to run the above query, it runs very slowly. An EXPLAIN query
reveals that there is no index for the product_id field when I've already added one, and
as a result the query takes any where from 20 minutes to 30 minutes to return a single
row.

My full EXPLAIN results
are:

| id | select_type | table |
            type | possible_keys| key | key_len | ref | rows | Extra
            |

+----+-------------+-------+------+--------------+------+---------+------+-------+------------------+
|
            1 | SIMPLE | table | ALL | NULL | NULL | NULL | NULL |157211 | Using where
            |
+----+-------------+-------+------+--------------+------+---------+------+-------+------------------+

It
might be helpful to note that I've just taken a look, and ID field is stored as INT
whereas the PRODUCT_ID field is stored as VARCHAR. Could this be the source of the
problem?