Usually DISTINCT is implemented as GROUP BY and triggers a table scan, see
http://dev.mysql.com/doc/refman/5.6/en/group-by-optimization.html, ie your query is likely being turned into ...
select deviceid
from userdeviceinfo
where created_on < '2015-02-10 18:30:00 and user_id is not null
group by deviceid;
... and you want to try to get Explain Extended to report ...
- `type` as range rather than index, and
- index use for group-by in the `Extra` column
- a reasonable number in the `filtered` column
A second or so for fetching 200k rows from a 500k-row table doesn't sound too bad. As I read the section on loose index scan in that manual page, putting the Group By column(s) first in the covering index might help. Worth a try.
How much RAM, what is innodb_buffer_pool_size?