Hi Scott,
First of all i must tell you not to use Paginate with conditions, it is known to be very overloading and sometimes can even bring you to a freeze. Use paginate_by_sql plugin instead, this will also solve your problem with the relation sorting