ActiveRecord is notorious for generating terrible, terrible SQL.
Edit: What I would expect to see would be index scan on device id, then sort + limit. So the important factor would be rows per device, not total rows.
The SQL was pretty simple I believe..select * from location where device_id = ? order by date_added desc limit 6...something like that.
Edit: Also, I don't know how much it matters, but MySQL probably only has ~256mb memory available to it (its hosted on a Xen box).
MySQL has a lot of very specific limitations about when it will and will not use the available indices. It also matters how you created the indices (one index on multiple columns vs multiple indices on individual columns).
For example, if you created a single index with the columns (date_added, device_id) MySQL would not be able to use the index since device_id is the second part of the index, not the first and thus not available for use in the WHERE clause.
See http://dev.mysql.com/doc/refman/5.1/en/mysql-indexes.html for more limitations.