Correlated attributes can still lead to the paradox, so long as the error measured parallel to the cutoff line (the "fuzziness" of the correlation) is greater than the slope of the cutoff line. Here are a couple cartoons to demonstrate. Denote each datapoint with I or E, depending on whether it's included or excluded in the region x + y > z.

Uncorrelated attributes:

   y
   │   ∙                
   │    ∙∙ IIIIIII      
   │     E∙∙IIIIIIII    
   │    EEEE∙∙IIIIIII   
   │    EEEEEE∙∙IIIII   
   │    EEEEEEEE∙∙III   
   │     EEEEEEEEE∙∙    
   │       EEEEEEE  ∙∙  
   │                  ∙ 
   └───────────────────x

Correlated attributes:

   y
   │  ∙              
   │   ∙∙   IIII   
   │     ∙∙IIIIII  
   │      E∙∙IIIII   
   │     EEEE∙III    
   │    EEEEEE∙∙     
   │     EEEE   ∙∙   
   │       E      ∙∙ 
   │                ∙
   └─────────────────x