I tested using a california and it worked, I then tested using a maryland address which failed.
Next i visited the USPS site to look up the calculation there, using maryland site. The USPS calculated was not returning a rate for the parcel shipping type to Maryland. It looks like that shipping type is not available in all areas.
In your site admin, i changed the shipping rule to use the priority shipping type instead of parcel, that seams to have fixed the rate lookup.