The definition of O(f(n)) means that the specified algorithm's running time is less than or equal to c*f(n), for some c > 0, and for some n > n' (i.e. large values of n going towards infinity).
So O(1) implies that the running time is less than some constant, say j.
And O(n) implies that the running time is less than some constant, say k, times n. So k*n.
Since we're assuming the lists are small, that means that n is a very small number. Now, depending on implementation, the values of j and k can vary as well. It is entirely possible for the O(1) constant time to be very long, say on the order of seconds. And it is also possible that the O(n) constant factor could be very short, say on the order of microseconds. In this case, with a small value of n, it is clear that the O(n) algorithm can outperform the O(1) algorithm (n microseconds vs. a few seconds).
The original statement is definitely correct - you really can't compare Big-O easily without considering constants, but mainly at small values of n. Once you get to larger values, the differences become more clear.