Flat tires can be troublesome as I have had experienced some of the same issues with my Griggio saw what you describe.
Mikes suggestion is what needs to be done next.
I would set a plum line, or good long level, to level up the machine, and as said place a straight edge on the wheels in the middle.
If you have a good chunk of timber jointed on 3 sides accurately, you will be able to rig/clamp it up against the wheels
and place a square against each side of the beam to true up the yaw angle .
Here is a 20" machine being tested for coplanar
You might find you need to place a washer behind a wheel possibly, as I've heard about folks
doing this on other saws in the past.
Would there be any side to side movement in the blade, so you wouldn't be able to set the guides tight (omitting the thrust guide), if the blade actually stayed on the wheels?
So there is no visible damage to the tires, are they both the same thickness?
How much meat are we talking here?
If you can take the wheels off easily, I would look to see if they are an even thickness throught
and not just seemingly even on the front of the tires looking at the wheels from inside the cabinet...
This fooled me and the only way I will make sure of this anymore, is by taking the wheels off...
or at least sliding them out, protruding from the saw cabinet so you can check them with a straight edge and a square which I can do with my heavy Griggio wheels.
I might ask how is the belt doing also?
These can be bought for very cheap.
Tom