What is it that tires first ,your lungs or arms? Maybe if its your arms you need some strength training? I have noticed I can go for much longer since I added a simple weights routine into my training.Also sounds like you could possibly do with adding some interval training into your routine- you can do that with your running and cycling, so you get used to pushing yourself then recovering ok.
Im no fitness expert,Im sure some guys will have far better advice!