The AS1130 will work fine with the ATmega128. The only hurdle I see really is that I'm not sure if the Arduinos Wire library will work with it. I don't see any reason why it wouldn't but at the same reason I don't know if it would, i'm not an expert on libraries. The only thing that would really "kill" the 128 chip in terms of compatability is if it had TWI (I2C) or not, and it does, so you are golden there. The 128 also has the same operating speed as an ATmega328P like on the popular arduino boards. The thing is that the PIC18F4550 has a max clock speed of 48MHz, so it may run a little slower than the video(if there is one, i'm sick so I don't feel like looking) but it should still do fine.
I'm actually incorporating this chip into one of my projects and I plan on using an ATtiny85 clocked at 10MHz to run it, I think it'll do fine. Only 2 ways to find out and I don't wanna pull up the datasheet! (Lazy! cause i'm sick (that excuse works wonders))
Regarding the programming language, the microcontrollers are generally written in C code and then uploaded via an ICSP or some other type of programmer.
Regarding the frames, hexadec will have to answer that one.