Everyone, this question is clearly talking about times in which the U.S. has armed foreign rebels, which would not include the French assisting the Continental Army in the American Revolution. Please stop posting about that.

Did the US ever arm Native Americans to eliminate another tribe?

Several commentators discussing American aid to Syrian rebels have floated US aid to Croatia during its war of independence as a potential model. The US/NATO provided military advisors, possibly intelligence and lifted major arms embargoes on Croatia and its allies, which were crucial in Croatia's Operation Storm, which decisively ended the war. NATO also conducted simultaneous air strikes against Serb/Yugoslav positions.

Another campaign I've been reading about lately is the CIA's covert programs in Laos in the early to mid 1960s. The CIA provided training, organizational direction, tactical advice, significant arms, funding and later massive air power to Meo (often called Hmong) rebels in order to disrupt North Vietnamese supply routes in Laos. This effort (spanning most of the war) built a fairly effective proxy army led by a Meo commander named Vang Pao. Later in the war (around 1968), however, the US switched from using those proxies as a ground force, and instead resorted to MASSIVE bombing campaigns which killed hundreds of thousands and ultimately failed catastrophically. It drove much of the population into the arms of the Pathet Lao, who quite quickly took over Laos after the Vietnam War ended. The Meo have been treated quite brutally ever since, suffering near-genocidal repression. Many, including Vang Pao, received asylum in the US.

The first example was successful in its aims. The second was not, though in my opinion, because it switched from supporting a decently effective guerrilla force to a massive air campaign. Before that switch, the policy of using such proxies was fairly effective in its objectives.

[Source on Laos is Robert Warner's Shooting at the Moon]

This answer might not be what you're looking for, depending on your definition of "arming" and "rebels". But you might already be familiar with it.

In 1953, the CIA and the MI6 funded Royalist factions of the Iranian army, which led to the overthrow of the democratically elected leader Mossadegh by a military government that would transfer all power to the monarch, Shah Pahlavi.

This was followed by 29 years of friendly US-Iran relations, no Iranian oil for the USSR and oppressive dictatorship by a corrupt tyrant for the Iranian people. So all in all, great success.

If I may ask the historians that specialize in the region, did we not do this extensively in Eastern Europe during the Cold War?

Further, in South America, has our track record been all bad?

The arming of italian rebels against Nazis and Fascist Social Republic during WWII is an example I believe. Other rebel formation were armed in all Europe, but since this is a strict sub I won't include them because I am not exactly sure who was armed and who wasn't. Were the Polish rebels armed by the americans? Don't know.

Everything almost worked completely flawlessly except after the war it was realised that also communist formations were armed and those brigades did not give up their weapons. They were ready for the comunist revolution in Italy that luckily never came for various reasons.

This is a well known fact in Italy, but wiki for reference anyway http://en.wikipedia.org/wiki/Italian_resistance_movement

Perhaps indirectly answering your question through reversal, the UN arms embargo on Yugoslavia is what directly enabled the genocide of the Bosnians, as Bosnia was surrounded by its enemies and couldn't geographically take advantage of the munitions black market like they could.

An example where explicitly NOT arming an upcoming state led to their detriment.

How do you define "worked out ok"? On a long enough timeline every military exercise can be considered a failure.

Short term, the U.S. has been successful in achieving its goals by arming Rebels: Iran, DRC, Afghanistan and Cambodia are good examples. In some instances the stated goal of government change may not have taken place but the unrest aided by arming rebels helped the U.S. achieve other goals.

In California, John Sutter armed Native Americans to protect his land from other Native American horse raiders. They ended up being in the California Battalion that fought on the American side of the Mexican-American War.

Edit: Source: Hurtado, Albert L. Indian Survival on the California Frontier. New Haven: Yale University Press, 1988.

Edit2: I'm not exactly sure how you would define 'rebels' but I guess Native Americans, to them, were seen as rebels in a way. Also, I don't know whether one could say it 'worked out.' The rights included for Indians in the Treaty of Guadalupe Hidalgo were greatly ignored by Anglos and the federal government so it didn't really benefit Native Americans in the end as they were discriminated against and taken advantage of. Especially after passing the Act for the Government and Protection of Indians in 1850. It was California's version of the Black Codes. The United States did gain a California and other territories though.

Arming the Mujahideen was rather successful when looking at the goals of the USA at the time. In 1989 the Soviets withdrew from Afghanistan. The Soviet Union was by far the largest threat to the United States and it's interests since WWII so thwarting its designs in Central Asia should probably be considered a huge success from that vantage point.

Some members of the Mujahideen then about 5 years after the withdrawal of the Soviet Union then later formed the Taliban with the help of the Pakistani ISI, but this is a fairly indirect consequence of the US intervention in my estimation.

This is a very large issue so I am not sure where to begin sourcing this. If you want more information on this event then let me know.