A star passage setting does not mean "the player can walk under this tile". It means "IF the player can get onto this tile, this particular image will be displayed in front of the player". It also means "look at the tile on the next layer down to get the passage setting, to determine whether the player can walk here or not".
Your map has two basic layers - a ground layer and a decorations layer. All the A tiles go on the ground layer. All the B-E tiles go on the decoration layer. Tiles on the decoration layer (B-E) can have a star as the passage setting; tiles on the ground layer can't.
If you draw ground tiles with X and then put decoration tiles with a star over them, you will not be able to walk on those tiles. The star tiles say "look at the passage setting on the ground tiles to see if the player can go here", and your ground layer tiles have an X, so the player will not be able to walk on them. If you draw ground tiles with O and then put decoration tiles with a star over them, you will be able to walk on those tiles. Again, the star tiles say "look at the passage setting on the ground tiles to see if the player can go here", and your ground layer tiles have an O, so the player will be able to walk on them.
Maybe you should show us a screenshot of the map in-game, highlighting the tiles you think you should be able to walk on, and then include screenshots from the Tileset window - one with the A tab so we can see what the ground tiles are set to, and one with the B-E tab that contains your starred tiles.
Are you using any scripts that alter passage settings or player passability behaviour?
