Costmap2DROS transform timeout

edit

I am trying to run amcl, move_base and map_server on my robot. Everything starts fine but after I get "Odom received" warning messages start to show up:

Costmap2DROS transform timeout. Current time: 1438775060.1538, global_pose stamp: 1438775056.1344, tolerance: 0.3000

and

[ WARN] [1438775074.022202129]: MessageFilter [target=map base_laser_link ]: Dropped 100.00% of messages so far. Please turn the [ros.costmap_2d.message_notifier] rosconsole logger to DEBUG for more information.

They come from the Costmap2D plugin. I runned tf_monitor and I got:

RESULTS: for all Frames

Frames:
Frame: /base_footprint published by unknown_publisher Average Delay: -0.0456822 Max Delay: 0.10752
Frame: base_front_laser_link published by unknown_publisher Average Delay: -0.545968 Max Delay: 0
Frame: base_link published by unknown_publisher Average Delay: -0.545971 Max Delay: 0
Frame: base_rear_laser_link published by unknown_publisher Average Delay: -0.545966 Max Delay: 0
Frame: odom published by unknown_publisher Average Delay: -0.108352 Max Delay: 0.0916446

All Broadcasters:
Node: unknown_publisher 82.2074 Hz, Average Delay: -0.360456 Max Delay: 0.10752

What could be the problem causing the timeout?

When viewing the frames, I see that robot_state_publisher publishes with 50 Hz but somehow all published links have a delay of -0.5 seconds, which cannot be possible!

I kept looking at it in real time with tf_monitor and the time of the most recent transform from robot_state_publisher is -0.5 for some time, then it jumps to +0.5. This is very confusing.

I kept tf_monitor running for few minutes and it seems like the delays are increasing:

RESULTS: for all Frames

Frames:
Frame: /base_footprint published by unknown_publisher Average Delay: 2.57823 Max Delay: 17.9659
Frame: base_front_laser_link published by unknown_publisher Average Delay: -0.408636 Max Delay: 0.626485
Frame: base_link published by unknown_publisher Average Delay: -0.40864 Max Delay: 0.626482
Frame: base_rear_laser_link published by unknown_publisher Average Delay: -0.408634 Max Delay: 0.626486
Frame: odom published by unknown_publisher Average Delay: 3.65717 Max Delay: 16.6323

All Broadcasters:
Node: unknown_publisher 82.0346 Hz, Average Delay: -0.124652 Max Delay: 1.20379