MySQL order by - one column conditional on another column
How about...

ORDER BY (`status` = 'complete'), `priority`


The expression status = 'complete' would resolve to 0 for non-complete, and 1 for complete... exactly the order you want... so you'd get all of the non-completed items sorted by priority, followed by all the completed items sorted by priority.