I'm experiencing the same thing. My script works perfectly on a 165MB file but fails after reading 900,000 bytes on a 22GB file.

My script uses a buffered bz2file.read and is agnostic about end-of-lines. Opening with "rb" does not help. It is specifically written to avoid reading too much into memory at once.

I have tested this script on:
Python 2.5.1 (r251:54863) (ESRI ArcGIS version) (WinXP 64-bit)
Python 2.7.1.4 (r271:86832) (64-bit ActiveState version) (WinXP 64-bit)
Python 2.6.4 (r264:75706) (Ubuntu 9.10 64-bit)

Check here for some really big BZ2 files:

http://planet.openstreetmap.org/full-experimental/