こんにちは。
１つ、アカウントの設定を確認してみてください。
Twitterのアカウントの設定に、「HTTPSのみ」という項目があり、デフォルトではオンとなっているはず・・・らしいです。
これがオンになっている場合、認証等の要求はhttpでも通るものの、実際にユーザのデータを取り扱おうとする要求を投げる際はhttpsによる通信でないとエラーになるようです。
もし、この設定項目に由るるものだとしたら、HTTPゲット/HTTPポストがSSL対応できるまでは、基本的になこったの利用は限定的(個々のユーザがセキュリティを下げる設定をしないと動かない)ということになりそうです。
他の原因としては、POST要求の際、本来はすべてのパラメータをBODYに入れてsignatureを付けるはずが、URLにパラメータを付加していて(BODY内の要素しか計算してなくて)signatureが合わないケース・・・というのも見かけましたので、れクエストを独自に生成している場合はチェックしてみてください。
どちらにしても、SSL対応は必要そうなので、手を付けてみます。