Why does common usage of "random" feel so incorrect?

Well, let's take the pedantry a step further and consult some references. Dictionary.com provides the following set of definitions:

adjective

1. proceeding, made, or occurring without definite aim, reason, or pattern: the random selection of numbers.

2. Statistics. of or characterizing a process of selection in which each item of a set has an equal probability of being chosen.
   

3. Building Trades.
   a. (of building materials) lacking uniformity of dimensions: random shingles.
   b. (of ashlar) laid without continuous courses.
   c. constructed or applied without regularity: random bond.

4. Informal.
   a. unknown, unidentified, or out of place:
   A couple of random guys showed up at the party.
   b. odd and unpredictable in an amusing way: my totally random life.

Idioms

7. at random, without definite aim, purpose, method, or adherence to a prior arrangement; in a haphazard way:

A cursory review of other references shows that the without reason or thought definition is widely accepted, and is often more prominent than technical meanings for the term. In other words, from the standpoint of the vernacular (which is to say the language popularity contest) you are not old skool; you are just wrong.

This is a hypothesis. To test the hypothesis, let's look back in time. Etymology Online says the origin of the word random is:

"having no definite aim or purpose," 1650s, from at random (1560s), "at great speed" (thus, "carelessly, haphazardly"), alteration of Middle English noun randon "impetuosity, speed" (c.1300), from Old French randon "rush, disorder, force, impetuosity," from randir "to run fast," from Frankish *rant "a running" or some other Germanic source, from Proto-Germanic *randa (cognates: Old High German rennen "to run," Old English rinnan "to flow, to run;" see run (v.)).

So in other words, the usages you are critiquing are in fact the old skool meanings for the word. Now, as you are no doubt aware, there is a wide variety of technical definitions for random with which the average layperson is not familiar. That same Wikipedia link provides the following meta discussion of randomness, titled:

Randomness versus unpredictability

Randomness, as opposed to unpredictability, is an objective property. Determinists believe it is an objective fact that randomness does not in fact exist. Also, what appears random to one observer may not appear random to another. Consider two observers of a sequence of bits, when only one of whom has the cryptographic key needed to turn the sequence of bits into a readable message. For that observer the message is not random, but it is unpredictable for the other.

And it goes on. The point I draw from this is that from the perspective of every day usage, there is no meaningful difference between appearing random and truly random. In particular, proving true randomness requires a rigorous statistical analysis, for which one would need to acquire far more data than is typically available.

---

On a personal note, I happen to agree with you. For the two examples you provided, I feel that much more precise term is arbitrary. But I don't mind being wrong; to answer your title question of why it feels wrong, it's your decision as to how right or wrong you want to be. Furthermore, it's up to you to decide the criteria for rightness. I tend to favor precision highly in my criteria for language use, but I think you can tell from the rest of my answer that I don't think many other people share that value.

---

On a final note, the criteria for correctness I allude to above depend heavily upon the context: who is the speaker, who is the expected audience, what is the topic being discussed? Your example of "The column and table names are random" is particularly tricky because it implies a technical context. As I am myself a programmer frequently working with databases, I would assume this sentence was talking about databases. In computer science, randomness has very particular definitions, none of which are close to the primary definition. Arbitrary is almost certainly the correct term in that sentence. After all, there is a wide difference between a naming schema of MyTable, MyOtherTable, SomeColumn etc. (arbitrary) and sʇɐƆʎʇʇǝɹԀ, d$fv$5vmZO^zc90h7, 3712#%58!efyox6!z66@j96 and Z̍a̟̳̮͍̘̰͎͝l̙̥̪̞̂͐͟ͅg̛̃̅͑o̰͖͇͙'̴̱̳͍̰̠̄́̍̐s̙̳͍͇͍ͦ͝T̤̹̱̜̜̱̔͗̂̚ä͊ͪ̆b̺͔̖̩͍͉ͪ̓̂́ͪl̞̖̯̗̣͕̊̓ͩ̃e͎̦̣̳͓͖̬ (actual randomness)

Note that I actually chose my 'random' names (with help from Upsidedowntext.com, LastPass and of course Zalgo Text Generator), so from a technical perspective, they're at best arbitrary enough to appear psuedo-random and at worst, just plain arbitrary.