By default, the navigation stack keeps obstacles in its costmap until a sensor sees through them. Are you sure that you have your laser set up to both mark and clear space? Without allowing the laser to clear, you won't clear out obstacles in the map. Also, if your laser is returning max-range values, they're likely being filtered out and not used for clearing space. This could also cause obstacles to stick around unexpectedly. Documentation on the "marking" and "clearing" parameter options for a costmap sensor source may also be useful, see:
http://www.ros.org/wiki/costmap_2d#Sensor_management_parameters