in reply to same query, different execution, different performance
Update: The OP is cross-posted at StackOverflow (Additional update: And on the DBI-users mailing list)
The db can only use the index if the parameter does not begin with a wildcard. The db can not know at prepare time whether or not your parameter will start with a wildcard. So when it makes the query plan at prepare time, it doesn't know whether or not it can use the index.
This is one of those times when it's best to not prepare the statement with bind parameters. But use $dbh->quote(...) on your parameter and just inline it into the SQL.