MYSQL ORDER BY Performance
What sometimes works in this situation is

SELECT * FROM
(
SELECT 
 PROJECT.PROJECTID, REQUEST.REQUESTID,
 SAMPLE.SAMPLEID,SAMPLE.OTHERSAMPLEID, 
 ILLUMINASEQPROTOCOL2.SAMPLEID 
FROM 
 ILLUMINASEQPROTOCOL2,
 PROJECT,
 SAMPLE,
 REQUEST, 
 ANCESTORS A1, 
 ANCESTORS A2, 
 ANCESTORS A3 
WHERE (
 ILLUMINASEQPROTOCOL2.RECORDID = A1.RECORDID AND 
 A1.ANCESTORID = SAMPLE.RECORDID AND 
 SAMPLE.RECORDID = A2.RECORDID AND 
 A2.ANCESTORID = REQUEST.RECORDID AND 
 REQUEST.RECORDID = A3.RECORDID AND 
 A3.ANCESTORID = PROJECT.RECORDID) 
AND  (
 (((ILLUMINASEQPROTOCOL2.RecordId &gt; 0) AND  
  ((SAMPLE.EXEMPLARSAMPLETYPE LIKE 'DNA') AND  
  (REQUEST.RecordId &gt; 0))) 
 AND  (PROJECT.RecordId &gt; 0))
) AS mytable 
) ORDER BY SAMPLE.RECORDID LIMIT 0,501;


i.e. transform your original query into a subquery within the outer SELECT. Then, put your ORDER BY and LIMIT as subclauses of your outer SELECT.

This should eliminate the bottleneck with the ORDER BY and LIMIT. The reason your query slows down with the ORDER BY is that the query has to retrieve all records and then SORT them - without the ORDER BY, the system can just spit out the first 500 records. 

It is puzzling that you do have indexes on the relevant fields. If what I have suggested doesn't work, you could post the table structures and the query execution plan.