To be submitted to PRL ; We present a search for anomalous production of events with two high-momentum leptons (electron or muon) of the same electric charge in \ppbar collisions at a center-of-mass energy of 1.96 TeV. We use a data sample corresponding to 1 \invfb of integrated luminosity recorded by the CDF II detector. We perform an inclusive selection with one lepton with transverse momentum above 20 GeV/$c$ and a second one above 10 GeV/$c$. The standard model backgrounds for this signature are small. Many extensions to the standard model, such as Supersymmetry and models with heavy Majorana particles decaying into leptons, predict the production of two leptons of the same electric charge. This search has better acceptance and examines between a factor of three and ten more integrated luminosity compared to earlier searches in the same channel, resulting in a significant increase in sensitivity. We predict $33.2±4.7$ events in our data sample and observe 44; the probability to observe an excess this large or larger is 9%. We also examine a second scenario with increased sensitivity for SUSY-like physics scenario in which a stable neutral particle escapes detection. In that case, we predict $7.8±1.1$ events and observe 13. The probability to observe an excess this large or larger is 7%.