Автокореляцию не пробовали? Вроде идеальная для этой задачи вещь. Легко ищет периоды сигналов со сложным спектром.
Цитата(Taradov Alexander)
Кроме применение мощного процессор противоречит самой идее простого гитарного тюнера.
А применение 30 рублёвого проца ни чему не противоречит? Юзайте LPC111x для этой цели. На 32 битное ядро не смотрите, смотрите на цену

По поводу "ошибок" китайского тюнера. Он скорее всего не ошибается. Если в звуке струны пропадает "основной" тон, а остаются только гармоники, то китайский тюнер не врёт. Но в девайсе собственного изготовления можно сделать такой алгоритм, что если самая низкая гармоника будет относительно максимальной например не ниже -10 Дб (или 20, по вкусу), то она будет определяться основной. И опять же можно сделать чтобы такой алгоритм был завязан на частоту, например работал на басовых и не мешал на других (если вдруг он будет там давать ошибки).