Beveling - Why won't old edges go away?
Not sure what is happening, but I do know that you do not have to select EVERY edge.  If you just grab each corner edge, you can hit delete and select vertices from the drop-down.  This will result with the other edges being deleted as well.