That's where the "as nearly practical" clause comes into play - any manoeuvre that involves moving from one lane to another involves temporarily straddling two lanes and it's clearly absurd to make changing lanes illegal. My understanding of that clause would be that if you're changing lanes you straddle the line, if you're overtaking you straddle the line, but within a reasonable amount of time (whatever "reasonable" means) you either move entirely to the other lane or return entirely to your original lane.
Your point also highlights that when a motorist straddles two lanes of traffic to pass a bicyclist, since they're not driving entirely within a single lane, it could be considered unlawful, or similar to DPS' claim, it is illegal. The law states "shall drive as nearly practical entirely within a single lane", so changing lanes entirely is more lawful than sharing a lane. Actually, when a motorist straddles two lanes to pass a bicyclist...that is lane splitting!