The "no valid host was found" error means the scheduler was unable to find a compute host with the resources necessary to boot your instance. This can happen legitimately if your instance requires more CPU cores or memory than is currently available, but it can also happen if there is a configuration issues on your compute hosts that makes them unavailable to the scheduler.

The first step is to make sure you're not running into an actual resource problem. If you're confident that you are not attempting to use more compute resources than you have available, the next step is to run nova-manage service list, which will produce something like this:

Binary           Host                                 Zone             Status     State Updated_At
nova-consoleauth mycontroller                         internal         enabled    :-)   2014-06-06 02:44:41
nova-scheduler   mycontroller                         internal         enabled    :-)   2014-06-06 02:44:41
nova-conductor   mycontroller                         internal         enabled    :-)   2014-06-06 02:44:37
nova-cert        mycontroller                         internal         enabled    :-)   2014-06-06 02:44:41
nova-compute     mycomputenode                        nova             enabled    :-)   2014-06-06 02:44:34

You want to see :-) for all of your compute nodes. If instead you see:

nova-compute     mycomputenode                        nova             enabled    XXX   2014-06-06 02:46:14

This indicates that your compute node is not properly communicating with the rest of your environment. The first place to look in this case is in /var/log/nova/compute.log on your compute host.

If nova-manage service list reports :-) for all your compute nodes, then you probably want to start by focusing on /var/log/nova/scheduler.log on your controller, which may have more information about why a valid compute host was not available.

Hopefully these steps will help you get closer to diagnosing your problem.