Two items that might cause the problem you encountered.
1) make sure that even your impassable elements have a valid (but very, very, high) impedance/cost value, not NODATA
2) your cost-raster should be in GRID format. I've had many problems with other raster formats (e.g., TIFF) not working properly in analyses.
Hope that helps!