Gallup Poll (National)
Of all the polls I looked at, the one most closely matching this claim is one long-running Gallup poll: Majority in U.S. Maintain Need for Third Major Party.

The question was:
"In your view, do the Republicans and the Democratic parties do an adequate job of representing the American people, or do they do such a poor job that a third major party is needed?"
Participants could also answer "no opinion". This polling question has been asked annually since 2003.
They described their methodology:
Results for this Gallup poll are based on telephone interviews conducted Sept. 9-13, 2015, on the Gallup U.S. Daily survey, with a random sample of 1,025 adults, aged 18 and older, living in all 50 U.S. states and the District of Columbia. For results based on the total sample of national adults, the margin of sampling error is ±4 percentage points at the 95% confidence level. All reported margins of sampling error include computed design effects for weighting.
Each sample of national adults includes a minimum quota of 60% cellphone respondents and 40% landline respondents, with additional minimum quotas by time zone within region. Landline and cellular telephone numbers are selected using random-digit-dial methods.
This is consistent with other polls in Gallup's Social Series polls.
Gallup cautions:
question wording [...] can introduce error or bias into the findings of public opinion polls
Public Policy Institute of California (State)
That same question was used by the Public Policy Institute of California without any change or criticism in a 2013 survey (p. 21). Their results (specific to California) had 49% for a "third major party needed", 13% "don't know", and 37% "existing parties adequate job" (my paraphrasing).
Suffolk University / USA Today (National)
In September 2015, Suffolk University/USA Today poll asked a slightly different question:
Do the two major parties – Democrat & Republican - do a good job of representing Americans’
political views, or do you think a third party or multiple parties is necessary?
The results were:
- Two parties: 30%
- Third party necessary: 29%
- Multiple parties necessary: 24%
- Undecided: 17%