uhm.. just from brain, for some ideas..
your billboard has a point, where it rotates around, and a "prefered up vector"..
now, you want the point-to-cam vector, simply to_cam = normalized(cam - midpoint).
next, you want a "right" vector, wich simply is perpendicular to your to_cam and the up vector, so you use a crossproduct.. to_right = normalized(cross(to_cam,up)) (or the other way around.. don't know from brain).
finally you want to adjust your up vector (but you let the original up vector still exist..), by crossing your current to_right vector with the to_cam vector..
to_up = cross(to_right,to_cam) (again, or the other way around.. )
with those three, you can transform all your billboard points of that specific billboard by these 3 vectors (they build a rotational 3x3 matrix.. look up orthogonal bases.. or so).
i hope that helps a bit..