Why does this recurrence give O(n) time? Given this following recurrence: $$T(n) =  T(n/2) + O(n)$$Find the final time complexity.

My first thought is $O(n\log n)$, since there is at most $\log n$ times the 
$O(n)$ will appear. 

However, if we adopt the following analysis and let $n=2^m$, then we have:

$$T(2^m) = T(2^{m-1}) + k(2^m) = T(2^{m-2}) + k(2^m + 2^{m-1})...$$

Which we can then condense to have the cost become:

$$2^m + 2^{m-1} .... + 1 = 2^{m+1} - 1$$

And so since the cost is $O(2^m)$, we have our $O(n)$ time as required.

Is the analysis valid? Because I have so very often seen proofs using recurrences of the form $T(n) = T(n/2) + ...$, and they all similarly concluded that there will be $\log n$ times of the relationship.

Which is correct?
Your second analysis is correct, and $T(n) \in \Theta(n)$. You can also use the Master Theorem to verify this.

The reason that the first "naive" analysis fails is that you don't have $O(n)$ at each step, you have $O(\frac{n}{2^{i}})$ where $i$ is how far down the recursion you've gone.

Ignoring the constant multipliers for the moment, this gives
$$
\sum_{i=0}^{\log n} \frac{n}{2^{i}} = \frac{\sum_{i=0}^{\log n}n}{\sum_{i=0}^{\log n}2^{i}} = \frac{n\log n}{2^{log n + 1}} = \frac{n\log n}{2 \log n} = \frac{n}{2}
$$

Your second analysis basically does the same thing, just using variable substitution instead.