The remove tile/floor tool actually adds an un-removable floor graphic under barrier blueprints that have an appropriate surface under them. (See screenshot, it even shows in the preview that it will add a surface graphic)
This surface created cannot be removed with the remove tool. The only way I found to remove it was to paint a new surface over it and then remove that surface.
Identified in 0.7.1c