What are the caveats of using global functions and/or classes with all-static methods?

The choice to use global functions, namespace functions, or static class functions, is forced by the language. I actually see no large fundamental difference between them and it comes down to naming conventions.

Consider the following function calls on an object:

user.get_name()

get_user_name( user )

user_db.get_name( user )

Given a proper naming convention they are all clear to read. Most programs will end up having a mixture of these approaches. This is due to limitations in the OOP paradigm, like being unable to extend 3rd party classes, or a quirk of the language (can't have globals, but can have static member functions). Obviosuly you'd want to be as consistent as possible within a project.

Functions that don't have a context (don't take a type instance), are usually clearer as static functions:

random_int( 4, 10 )

random.next<int>( 4, 10 )

Many languages require you instance something, like var r = new random(), and that often bugs me. Forcing instantiation is also a problem since it implies something more than you want. Does this random instance r have meaning? Do I need to share it, or have hundreds of them. Static functions resolve this problem.

NOTE: This is all about global and/or static functions. Global variables are a whole other beast entirely, and Ben Halpern's post applies.

I feel like this article explains it well:

Non-locality -- Source code is easiest to understand when the scope of its individual elements are limited. Global variables can be read or modified by any part of the program, making it difficult to remember or reason about every possible use.
No Access Control or Constraint Checking -- A global variable can be get or set by any part of the program, and any rules regarding its use can be easily broken or forgotten. (In other words, get/set accessors are generally preferable over direct data access, and this is even more so for global data.) By extension, the lack of access control greatly hinders achieving security in situations where you may wish to run untrusted code (such as working with 3rd party plugins).
Implicit coupling -- A program with many global variables often has tight couplings between some of those variables, and couplings between variables and functions. Grouping coupled items into cohesive units usually leads to better programs.
Concurrency issues -- if globals can be accessed by multiple threads of execution, synchronization is necessary (and too-often neglected). When dynamically linking modules with globals, the composed system might not be thread-safe even if the two independent modules tested in dozens of different contexts were safe.
Namespace pollution -- Global names are available everywhere. You may unknowingly end up using a global when you think you are using a local (by misspelling or forgetting to declare the local) or vice versa. Also, if you ever have to link together modules that have the same global variable names, if you are lucky, you will get linking errors. If you are unlucky, the linker will simply treat all uses of the same name as the same object.
Memory allocation issues -- Some environments have memory allocation schemes that make allocation of globals tricky. This is especially true in languages where "constructors" have side-effects other than allocation (because, in that case, you can express unsafe situations where two globals mutually depend on one another). Also, when dynamically linking modules, it can be unclear whether different libraries have their own instances of globals or whether the globals are shared.
Testing and Confinement - source that utilizes globals is somewhat more difficult to test because one cannot readily set up a 'clean' environment between runs. More generally, source that utilizes global services of any sort (e.g. reading and writing files or databases) that aren't explicitly provided to that source is difficult to test for the same reason. For communicating systems, the ability to test system invariants may require running more than one 'copy' of a system simultaneously, which is greatly hindered by any use of shared services - including global memory - that are not provided for sharing as part of the test.