いつも普通に話せる年上の人と電話で話し切る間際「お疲れ様でした」と言ったらとても不快だと言われました。仕事や用が終わった時、目上の人に「ご苦労様」と言うのは大変失礼なことだとは思いますが、笑顔で頭を下げつつの「お疲れ様ぁ～！」はどんなに上の人にでも使えるねぎらい、挨拶でありけっして失礼には当たらないと認識しています。しかも仕事の場合メールの一行目にも入れています。　結局不快を示した人とは話が平行線で相手も譲らないのですが、世間一般で使っていると考えられる「お疲れ様」という言葉、果たしてどんな位置にいるのでしょうか？

「お疲れ様」も「ご苦労様」も労いの言葉です。

「労い」というのは、【同等か目下の者に対するいたわり】を意味します。

つまり、目下に使う言葉を目上の人に使うと失礼ということなのです。

「お疲れさん」だと上からの言葉に聞こえるのを「様」をつけることによって丁寧語のように囚われがちですが、実はそうではないという一例です。

とはいえ、私も会社員の頃、「お疲れ様です」を社内で使っておりました（ですが、殆どが後輩だったので、今思うと問題なかったのかもしれません）。

上司と長時間話していた時は「時間を割いてくださり有難うございます」です。

言葉は生もののようです。

私が中学生の頃は何でもかんでも「超」を付けて話すのが流行り、親世代から注意されましたが、今は商品名に使われたり、道路標示にも使われますから世の中に認知されてきたのだと思います。

「お疲れ様」は、今、その狭間にあるのではないでしょうか？

普通に使う事がある人もいれば、目上の人間に使うべきではないと思う人もいるということです。

ただ、会社に勤めている以上、上司（目上の人）が不快だというのでしたら、後輩が折れるべきです。

その方は上下には厳しい方なのでしょう。

どちらも決して間違いではないですが、日本語として正しいのは相手の方ではないかと思います。