どうも、shibuso です。春イベントですね。私の資源力は53 万です。（実際には80 万ぐらいあります:P）
既に動いているシステムのバージョンってなかなか上げられないのが困りモノです。今回も古いRuby を使っていたがために問題にぶつかったので、今となってはあまり需要は無さそうですがまとめてみました。
まず問題が起こった環境はRuby 1.9.2p320 とRails 3.1.3 で動いていたところにdelayed_job_active_record 4.0.1 （現時点で最新）を入れた状態でした。最初Ruby 1.9.3p448 を使用していたところ問題なく動いていたので、恐らくRuby 1.9.3 以降では起こらないのではないかと思います。
問題はdelayed_job を呼び出すためにdelay メソッドを呼び出して実行した時に、DB のdelayed_jobs テーブルにあるhandler カラムに入るパラメータの一部に間違いがあるために正しく実行されないというものです。以下、適当なModule を非同期で呼びだそうとした時の正しい例と間違った例を記載します。
呼び出す箇所
HogeHoge.delay.hoge
正しい値の例 (Ruby 1.9.3p448 + delayed_job_active_record 4.0.1)
object: !ruby/module HogeHoge
間違っている値の例 (Ruby 1.9.2p320 + delayed_job_active_record 4.0.1)
object: !ruby/object:Module {}
ここの情報が間違っているためにModule を上手く呼び出せず、結果としてNoMethodError が発生していました。
どうもこの現象は当時それなりに問題になっていた模様で、検索するとGitHub のIssue でやり取りが見れました。2 年前ですが（苦笑）
NoMethodError with delayed_job · Issue #323 · collectiveidea/delayed_job · GitHub
このIssue の中にある投稿で解決できた報告があり、且つ環境が似ていたので同じくdelayed_job 2.1.4 を入れてみたところ動くようになりました！
Gemfile
gem delayed_job, '2.1.4'
原因は何か複数あるような感じで、このIssue を見ているとHeroku 関連の問題もあるみたいでした。ちなみに今回私が経験したのはHeroku ではなく普通のサーバーと手元のVM 環境で、nginx + unicorn です。