Slow Response on Count in MySQL join

I am bound in this project to using mysql.
My problem is I've never had to use "count" in a join, and there must be a better way to do this because it is taking an incredibly long time.
The query is

   $Q = "FROM AccountsMain INNER JOIN PricingMain2 ON PricingMain2.AppID = AccountsMain.AppID
            WHERE PricingMain2.Status != 'Limbo' AND PricingMain2.Status != 'Deleted' AND PricingMain2.ModifyDate > '$RecordDate'";

Select allOpen in new window

I then do this to get the total count for pagination

   $Result = mysql_query("SELECT count(*) ".$Q;
   if(!$Result){$Error[] = "Database Failure [1]";}
   else
   {
      $query_data = mysql_fetch_row($Result);
      $TotalCount = $query_data[0];
   }

Select allOpen in new window

Then this

   $GSReq = "AccountsMain.AcctName"; 
   $Limit = 'LIMIT '.($PageNo - 1) * $PageSize.','.$PageSize;
   $TotalPages = ceil($TotalCount/$PageSize);
   $Query = "SELECT * ".$Q." ORDER BY ".$GSReq." ".$Limit;

Select allOpen in new window

This process takes almost 60 seconds on a mere 10,000 records.