It's plenty of power. The R9 295x2 has a tested maximum average power consumption of about 500w, and there is no way the rest of your system is going to use anything near 250w. I think an 850-1000w unit, IF it were a good model, would be better in general due to giving you a little more overhead to cover spikes or other system considerations, but as Jon has already told you he was running his R9 295x2 on an RMx750, so if you needed any proof that that power supply is capable enough of running that graphics card, well, that's pretty much all it should have taken to provide that for you. Not to mention there are several PROFESSIONAL, not "they said", reviews out there showing that full system power consumption is pretty well below 750w when using that card for the majority of systems.
Now, if you were using some kind of very high TDP processor, like some of the HEDT models, it might be a different story, and if you plan to upgrade your platform anytime in the next 5 to 7 years with a CPU that is a very high TDP model, then it might be a bit more indicative of the need for a higher capacity power supply as a necessity rather than just as a common recommendation.
So yes, it will run on an RMx750. An 850-1000w unit, IF it is a very good model, might be better, IF it is something that you can financially afford to do. If not, I think the RMx750w should be ok based on it's quality and the numbers alone.