In our mostly large applications, we usually have a only few locations for "constants":

One class for GUI and internal contstants (Tab Page titles, Group Box titles, calculation factors, enumerations)
One class for database tables and columns (this part is generated code) plus readable names for them (manually assigned)
One class for application messages (logging, message boxes etc)

The constants are usually separated into different structs in those classes.
In our C++ applications, the constants are only defined in the .h file and the values are assigned in the .cpp file.
One of the advantages is that all strings etc are in one central place and everybody knows where to find them when something must be changed.
This is especially something project managers seem to like as people come and go and this way everybody can change such trivial things without having to dig into the application's structure.
Also, you can easily change the title of similar Group Boxes / Tab Pages etc at once.
Another aspect is that you can just print that class and give it to a non-programmer who can check if the captions are intuitive, and if messages to the user are too detailed or too confusing etc.
However, I see certain disadvantages:

Every single class is tightly coupled to the constants classes
Adding/Removing/Renaming/Moving a constant requires recompilation of at least 90% of the application (Note: Changing the value doesn't, at least for C++). In one of our C++ projects with 1500 classes, this means around 7 minutes of compilation time (using precompiled headers; without them it's around 50 minutes) plus around 10 minutes of linking against certain static libraries.
Building a speed optimized release through the Visual Studio Compiler takes up to 3 hours. I don't know if the huge amount of class relations is the source but it might as well be.
You get driven into temporarily hard-coding strings straight into code because you want to test something very quickly and don't want to wait 15 minutes just for that test (and probably every subsequent one). Everybody knows what happens to the "I will fix that later"-thoughts.
Reusing a class in another project isn't always that easy (mainly due to other tight couplings, but the constants handling doesn't make it easier.)

Where would you store constants like that? Also what arguments would you bring in order to convince your project manager that there are better concepts which also comply with the advantages listed above?
Feel free to give a C++-specific or independent answer.
PS: I know this question is kind of subjective but I honestly don't know of any better place than this site for this kind of question.
Update on this project
I have news on the compile time thing: 
Following Caleb's and gbjbaanb's posts, I split my constants file into several other files when I had time. I also eventually split my project into several libraries which was now possible much easier. Compiling this in release mode showed that the auto-generated file which contains the database definitions (table, column names and more - more than 8000 symbols) and builds up certain hashes caused the huge compile times in release mode.
Deactivating MSVC's optimizer for the library which contains the DB constants now allowed us to reduce the total compile time of your Project (several applications) in release mode from up to 8 hours to less than one hour!
We have yet to find out why MSVC has such a hard time optimizing these files, but for now this change relieves a lot of pressure as we no longer have to rely on nightly builds only.
That fact - and other benefits, such as less tight coupling, better reuseability etc - also showed that spending time splitting up the "constants" wasn't such a bad idea after all ;-)
Update2
Since this question still receives some attention:
Here is what I've been doing in the past few years:
Put every constant, variable, etc exactly in the scope that is relevant for it: If you use a constant only in a single method, it is OK to define it in that method. If a single class is interested in it, leave it as a private implementation detail of that class. The same applies for the namespace, module, project, company scope. I also use the same pattern for helper functions and the like. (This may not apply 100% if you develop a public framework.)
Doing this increased reusability, testability and maintainability to a degree where you not only spend less time compiling (at least in C++), but also less time on bugfixing, which leaves you more time for actually developing new features. At the same time, developing these features will go faster since you can reuse more code more easily. This outweighs any advantage the central constants file might have by a magnitude.
Take a look at especially the Interface Segregation Principle and the Single Responsibility Principle if you want to know more.
If you agree, upvote Caleb's answer since this update is basically a more general take on what he said.

Constants that are specific to a class should go in that class's interface.

Constants that are really configuration options should be part of a configuration class. If you provide accessors for the configuration options in that class (and use them in place of the constants elsewhere), you won't have to recompile the whole world when you change a few options.

Constants that are shared between classes but which aren't meant to be configurable should be reasonably scoped -- try to break them out into files that have particular uses so that individual classes only include what they actually need. This again will help reduce compile times when you change some of those constants.
