My plantronics 835 will not pair with my EVO

Just a guess, if it was paired with another phone previously, try defaulting the headset's settings. (I'm assuming you have tried turning off/on the headset and had it in pairing mode for the phone to see it). My headset had troubles when first seeing the EVO and I did the factory settings for the headset.