If you've finished his quest, you can't recruit him, or if you have positive reputation with Caesar's Legion.
Does he say something about your reputation?
If I'm correct, it depends on if your reputation is too high for the Legion or too low for the Followers
why is your anus itchy?
Serious answer: If you currently have ED-E as a companion, fire it (send it back to the Lucky 38), that should allow you to rehire Arcade. Then also rehire ED-E, if you want to. Arcade will not leave you if you have positive Legion reputation, he'll only leave you if when you meet up with Legate Lanius at the latter stages of a Legion playthrough/ending.