Most databases have odd behavior when working with dates,
If I remember correctly, MySQL stores datetime as a long integer and will convert the strings from the query to long int for processing it. However, I'm not sure about that and this approach should be way faster. A problem with the keys might be, that the primary key spans several fields and not only starttime, i.e., the key will probably be stored as a hash and not an integer.
A simple solution might be to modify the table to reflect a better structure for the mentioned query, e.g., by introducing another index for starttime, as also mentioned by gadget.
BUT, the table is not a pluto/LMCE table but a Myth table if I understand correctly. Is this correct? I think we should not alter these tables but rather use the vanilla packages.
Another approach could be to use an on-update/on-insert trigger to fill a temporary table with the required information.
Thom, do you know which query is used by MythTV itself?