Arkansas is the only state in which no Libertarian Party nominee has ever been on the ballot for any partisan office (except President). The state requires 10,000 signatures to place a new, or previously unqualified party, on the ballot. The Arkansas Libertarian Party is raising money to pay for a petition drive for 2012 and says it now is one-fourth of the way toward its goal. See the party web page here.
Parties in Arkansas must complete the petition in 90 days, but they choose their own 90-day period. The only parties that have qualified in Arkansas (for office other than President) in the last 40 years have been the Reform Party and the Green Party. Arkansas lets parties on the ballot for President only with a petition of 1,000 names, and many parties have qualified for presidential-only status.
Before 1971, Arkansas let any party on the ballot for all office, just by request. No petition was needed.