Kirchhoff's laws give relations that stem from the topology of the circuit --- how the components are connected. But they don't take any account of what kind of components are making those connections.
So you also need to have some information about the behavior of the elements. For example, an ideal resistor passes a current proportional to the voltage applied to it (a relationship called Ohm's Law). Or that an ideal voltage source provides a fixed voltage, allowing any amount of current to pass through it. As DanielSank reminded me, the equations describing the individual circuit elements are called constitutive relations.
With either KCL or KVL and the equations describing the components making up the branches of the circuit, you can solve any realistic circuit. This is called mesh analysis when done with KVL, or nodal analysis when using KCL.
It's also possible to draw a nonsense circuit that can't be solved by any method at all --- for example with two different-value voltage sources connected in parallel. These "circuits" are simply logical contradictions, not modeling any real physical circuit, so there's no loss by not being able to solve them.
Another limitation, KCL and KVL apply only to lumped circuits. That is, circuits whose physical dimensions are much smaller than the wavelengths associated with the highest frequency signal present in the circuit. In large circuits you might see effects like radiation or transmission line delay that are not modeled by straightforward application of Kirchhoff's laws, although it is in many cases possible to produce an adequate equivalent lumped element model for distributed circuit elements to allow Kirchhoff's laws to be applied to the rest of the circuit they're connected to.
I should also add, that while linear circuits (composed of voltage sources, current sources, linear resistors, and linear controlled sources) can be solved by straightforward application of linear algebra to the KVL/KCL equations and the constitutive relations, it's possible to construct nonlinear circuits that are extremely difficult to solve, and for any particular numerical solution technique there's likely to be some circuit for which it fails.