The most salient acid-fast bacteria are Mycobacterium spp., which are part of a phylum of gram-positive bacteria called Actinobacteria. This classification is based on 16S rRNA sequencing. However, based on genetic conservation, this paper makes the claim that they are more closely related to gram negative bacteria.
Acid-fast bacteria are characterized by cell walls rich in mycolic acids. This characteristic causes both poor stain penetration and high stain retention which forms the basis of acid-fast stains. However, it also means that crystal violet will not penetrate the cell wall efficiently. Thus their gram reaction is variable and they generally stain light purple. The result is dependent on technique as well as mycolic acid content variation between genera (Nocardia spp, for example, are less acid-fast and stain gram positive). Needless to say, their cell walls don't fit well with the classic dichotomy of thin versus thick peptidoglycan which the gram stain differentiates between.
Example Gram Stains:
For comparison, the left image is of Bacillus subtilis, a gram positive, non-acid-fast bacilli. In the middle is M. phlei and on the right is M. smegmatis, both of which are acid-fast but show a weakly positive gram reaction. Images from Napa Valley College.
B. subtilis is again on the left for comparison. In the middle is M. fortuitum staining positive but more weakly than B. subtilis. On the right is N. astroides which is partially acid-fast but stains strongly gram positive. Images from Microbe Canvas.