Can you make an object always follow the surface of another mesh with some kind of projected line?
I came up with two methods which might help you. See this blend file for an example of both of them:


This is what the results look like (the deforming cube is shrinkwrap method, the curvy one is the curve method):


Curve deformed by curve and used as path


Create a 3D curve to define the branch (and use Bevel and Taper Curves to give it thickness etc.)
Animate the branch curve any way you like (I used hooks, but it should be irrelevant)
Create another 3D curve to serve as a path for the bug and painstakingly put curve points around the branch curve's resulting mesh and don't forget to adjust the tilt in case you want the bug to around the branch
Add a Curve-Modifier to the bugs path and choose the branch curve as deformer and make sure you check the button so the modifier is applied to the curve points, not the resulting mesh: 
Add a Follow Path Constraint to your bug and choose the path for the bug
Done!


Shrinkwrap-Contraint

This one is a bit simpler and might be sufficient depending on the complexity and strength of your branches animations.


Create a 3D curve to define the branch
Create a mesh for the branch
Add a Curve-Modifier to your mesh and choose the branch as curve deformer
Animate the branch curve any way you like (I used hooks, but it should be irrelevant)
Add a Shrinkwrap-Constraint to your bug and choose the branch mesh as target