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?