I recently tried to run
bundle install --verbose
Unmet Dependencies: ["spicycode-rcov", "tenderlove-frex"]
Fetching gem metadata from http://rubygems.org/
Query List: ["spicycode-rcov", "tenderlove-frex"]
Query Gemcutter Dependency Endpoint API: spicycode-rcov tenderlove-frex
Fetching from: http://rubygems.org/api/v1/dependencies?gems=spicycode-rcov,tenderlove-frex
Query List: 
I've encountered this behaviour several times. Bundler is likely not stuck, but rather is exploring a degenerately large search space of possible gem versions. You can get detailed debug information about how it is evaluating possibilities by setting env var
DEBUG_RESOLVER=1. Read "How does Bundler bundle?" to understand the algorithm and the output of of the resolver trace.
I worked around the problem by identifying a gem from the trace over which Bundler was consistently backtracking and retrying many different candidate versions and constraining the versions to greater than some recent version. This often helps Bundler substantially reduce the search space and complete its evaluation rapidly. Of course, the constraint you add may produce an unresolvable conflict with another gem's requirement, in which case you can incrementally relax your constraint until it's compatible.
I have a personal TODO to go back to one of these degenerate resolve conditions and transform it to a set of dependencies and version histories that can all be made public so I can submit a reproducible issue to the Bundler devs. (Many of our gems are private to our company.) This comment in the source indicates they think the algorithm always completes in reasonable time, but empirically there are difficult cases that have valid solutions that can't be solved with hours of computation.
If your situation turns out to be akin to mine, but relies entirely on public gems, it would be a service to the community if you could make the problem gemfile and gemset public and submit an issue to Bundler so someone who knows the algorithm deeply can improve it.
Issue #2030 indicates that there may be a bug where the resolver actually gets stuck in an infinite loop. If you see evidence of that, you may want to submit your gemfile to that issue, especially if your reproduce case is smaller than the already submitted one(s).