Honestly there is basically no such thing as a paleo diet not working. You may need to tinker with various things (can't really comment more on this without detailed diet/exercise information), but you may also just still be suffering from carb withdrawels. The important thing to note is that there is just NO way that reintroducing grains and legumes is going to improve your health beyond satisfying your current cravings. Grains have low nutritional value and are very potent GI irritants, and both studies and empirical data shows that everyone is better off removing them from their diet.
If you still decide to reintroduce them, then none of us here can really do much more than wish you luck.