LBP5500ですね。ヘボ大学生なので回答に自信がないですが・・・・
インターネットで設定する、と書いてありましたので多分前の方はプリンターと各パソコンはＬＡＮで接続されていたのではないかと思います。（貴方様の会社では多分複数台のＰＣからＬＢＰ５５００１台で印刷が出来ていたと仮定します。）
各パソコンに接続されたＬＡＮケーブルを集約する機械（ハブ）というものにプリンターのＬＡＮケーブルも繋がっているのではないかと思います。 回線業者が変わってしまい、パソコンのプリンター設定が以前のままになっていることが原因ではないかと推測されます。
複数台のパソコンで１台のプリンターをＬＡＮ接続で共有する場合、プリンターにもＩＰアドレスという識別用のアドレスが割り振られるのですが、多分それだと思います。
最初に、プリンタの操作パネルの所で、オンラインランプがついていることを確認してください。
点いていなかった場合、「オンライン」ボタンを押してください。
一度それで印刷を実行してみてください。
下記はそれでも印刷できなかった場合の方法です。
まず、LBP5500のCD-ROMを探してください。
見つかりましたら・・・・
・設定をしたいパソコンにCD-ROMを入れる→自動でCDから何か立ち上がるのでNetSpotDeviceInstallerをクリックする。
・CD-ROMから起動（TCP/IP版）をクリック（使用許諾うんぬんが出た場合は「同意する」をクリック）
・デバイスリストが出てきますので、そのリストの一覧の中で未設定になっているもの 又は LBP5500 を探し出します。
・LBP5500の文字の上で右クリックし、初期設定をクリック→次へをクリック
・初期設定が開いたら「IPアドレス設定方法」の所をDHCPへ変更する
・そして下にあるOKボタンをクリックします。
あとは全部閉じてもう一度印刷が出来ないか試してみてください。
本来は部署の管理者が細かい設定を握っているため、これ以上は自分でも限界です。
インターネット上の画面から設定をしていたというのは「リモートUI」という機能なんですが、
プリンタがどのアドレスなのかがわからなくなっている今、現物を見ない限り難しいですね。
最悪、業務にも支障が出るならば業者を呼んで再設定して頂くしかないかなと思います。。。
念のため、キャノンのマニュアルダウンロードページへのリンクを張っておきます。
http://cweb.canon.jp/manual/lasershot/5500.html上記から
・ＵＩリモートガイド
・ネットワークガイド/本編
以上を参照してみてください。ネットワークガイドをとりあえず読んで自分なりに問題の切り分けを行ってみた推測です・・・
