The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs.