Hi,
there should be no issues (still check BUG Navigator for your HW/SW combination).
NBAR classification and marking can be done incoming or outgoing. With latest software you even can mark DE Bit and f.e. DSCP at the same time.
Be aware that LFI would also fragment VoIP packets in case you choose the size too small, which is NOT what you want to do!
A good starting point could also be "auto qos voip" on the framerelay interface, from which you can start to adjust the resulting config to your special needs.
The service-policy should be applied to the FR class not directly to the interface. Depending on what you want to do, enable frame-relay traffic shaping as well.
In case you need more detailed help let us know more details about your specific setup and requirements.
Regards
Martin