Yep, this does seem like a cron issue.
Core Control plugin is good to diagnose cron tasks (among other things).
I am still unsure what is the reason of you getting overrun with feed transients. However I had written some code that might help with automatic cleanup.