This is a very good source that I'm reading too! >> http://blog.tkjelectronics.dk/2012/09/a-practical-approach-to-kalman-filter-and-how-to-implement-it/
This project might provide some hints:http://students.iitk.ac.in/eclub/assets/documentations/summer12/self-balancing-bot.pdfCheck out the PID Tuning section.
Perhaps your tuning knobs don't cover the stable region. Try changing the range on your various tuning knobs (one at a time) to allow for finer tuning as you approach usable settings.
Try to tune your motor's speed response first, making sure that it's speed can be controlled linearly before tuning the balancing PID.
Should I map the speed of 0->255 to something like 30(or so)->255 to compensate