Du ahnst es vielleicht schon: Microsoft hat den +-Operator so definiert, dass sein Ergebnis ein int ist, selbst wenn beide Operanden bytes sind. Da es keine implizite Konvertierung von int nach byte gibt (aus gutem Grund), mußt Du dein Ergebnis casten.
Die subtilen Hintergründe dafür möchte dieser MSDN-Blogbeitrag erhellen.

Ergänzung: in Java ist das übrigens auch so gelöst, auch da ist das Ergebnis einer byte-Addition ein int.