Conversion to Dalvik format failed with error 1

仕事で開発しているアプリで、apkを出力する際に以下のエラーメッセージが表示されて、apkが作成出来ない状態になりました。

Conversion to Dalvik format failed with error 1

このエラーメッセージで検索すると、同じ症状に遭遇している人は結構いるらしいことがわかります。
ただ、どのサイトも解決策がはっきりしない印象です。
この症状について書かれているのはだいたい以下の点です。

・Androidのソース形式のライブラリを参照するプロジェクトで起きている
・プロジェクトのcleanを行ったら直った
・Eclipseに-cleanオプション付けて起動し直したら直った
・binとgenディレクトリを削除したら直った

自分もこのあたりは試したのですが、直りませんでした。
その後、いろいろ試しているうちに、binの中のファイルをたまたま開きました。すると、Eclipseから同期されてない状態になっていたのです(refreshしろと言われる状態)。
なんとなくあやしいと思い、binディレクトリをリフレッシュした後、apkの作成を試してみると…ちゃんと出力されるではありませんか！

ただ、これで完全に解決したわけじゃないのですよね…。
その後、プロジェクトをcleanしたら、また同じ症状が…。またbinをリフレッシュしたり、もう一回cleanしてみたりしていたら、再びapk作成が成功…。よくわかりません。
原因を特定出来るようなエラーメッセージがどこかに出力されてると良いんですが…(されてるけど英語を読めてないだけかな…？)。
一応apk作成に成功する(こともある)ようになったので、あまりコレばかりに時間をかけるわけにもいかず、よくわからないまま、また必要性になったら調べることにしました。

 うーん、どうもすっきりしません。

ご存知の方がこの記事を読まれましたら、コレどうしたら良いのか是非とも教えてくださいませ。よろしくお願いします。

追記：
[menu - Project - Build Automatically]のチェックを付けていると失敗しやすいような気がします。