MySQL: 2 separate queries run very fast, combined query with OR runs very slow
In my experience though, doing anything with an OR condition can have horrible implications when running queries, have you considered running this as two separate queries and then combining the results?

E.g.

SELECT * FROM (

    SELECT inet_ntoa(src) as source, inet_ntoa(dst) as dest,
        firewall.name as fw, proto.proto, service, action.action, 
        sum(count) as hits, max(date) as lastused, rule_uid.rule_uid 
    FROM log, action, firewall, proto, rule_uid 
    WHERE ( rule_uid.id = log.rule_uid ) 
            AND ( proto.id = log.proto ) 
        AND ( log.action = action.id AND action.action='accept' ) 
        AND ( log.orig = firewall.id) 
        AND ( ( src &gt;= inet_aton('0.0.0.0') 
                AND src &lt;= inet_aton('255.255.255.255') ) )
        AND ( ( xlatedst &gt;= inet_aton('173.82.122.94') 
                AND xlatedst &lt;= inet_aton('173.82.122.94') ) ) 
    GROUP BY src, dst 
    ORDER BY hits DESC, dst

    UNION ALL

    SELECT inet_ntoa(src) as source, inet_ntoa(dst) as dest,
        firewall.name as fw, proto.proto, service, action.action, 
        sum(count) as hits, max(date) as lastused, rule_uid.rule_uid 
    FROM log, action, firewall, proto, rule_uid 
    WHERE ( rule_uid.id = log.rule_uid ) 
        AND ( proto.id = log.proto ) 
        AND ( log.action = action.id AND action.action='accept' ) 
        AND ( log.orig = firewall.id) 
        AND ( ( src &gt;= inet_aton('0.0.0.0') 
                AND src &lt;= inet_aton('255.255.255.255') ) )
        AND ( ( dst &gt;= inet_aton('173.82.122.94') 
              AND dst &lt;= inet_aton('173.82.122.94') ) ) 
    GROUP BY src, dst 
    ORDER BY hits DESC, dst

) ORDER BY hits DESC, dst
LIMIT 100;


That may do the job, or something similar :)