This is most likely a firmware problem, not a Linux
problem. What make/model is the drive? My ASUS
for instance (if run under windows, with the native
software that came with it) will lock itself to the region
that was played 4 times first.
I currently have 4 different DVDs active under Linux
(on 3 different machines) and all of them play all regions
just fine (after I reset the ASUS, that is ;}) ...