As I was falling asleep last night, I thought of something else. My original reply would explain slowness for fetching each row, but not necessarily the first. The issue that you're seeing implies that the database engine is having a hard time locating the rows. However, with 40,000 rows, it should be able to tablescan the table in a few seconds, so there's something going on here. There's another reply in this node that suggests that MySQL fetched the entire resultset before returning the first row. If you can confirm that, then that might your issue you are returning a lot of data...
Feel the white light, the light within
Be your own disciple, fan the sparks of will
For all of us waiting, your kingdom will come