Can a vectorized computation always be parallelized? If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, Mathematica, Matlab, or seek clarification.

Are there situations when a vectorized (aka element-wise application of a function or array programming (AP)) computation cannot be parallelized?

When coding, I frequently replace loops with a vectorized computation, if possible. At times, it's an interesting exercise or (arguably) makes the code more readable. Other times, in hopes of parallelizing it in the future, if need be. 

Is there a constraint that would prevent me from parallelizing a vectorized code.

Vectorization example
Note that even seemingly tight loop can be vectorized. For example, cumulative sum of vector elements (1, 2, 3) can be transformed to a matrix form ((1,1,1),(0,2,2),(0,0,3)) and then vectorization is done as column sums producing the desired (1,3,6) cumulative sum. However, vectorization of fibonacci sequence is unlikely(?).

Many thanks for your explanations and references.
If there are dependencies between loop iterations, then the loop cannot be parallelized.  Depending upon the precise definition of "vectorized" you have in mind, your definition might imply that there are no dependencies -- or it might not.

Some examples:

foreach i in S:
    B[i] = f(A[i])


is parallelizable if f is a pure function and A,B don't alias (have no overlap).  (But it is in general not parallelizable if f writes to global state or performs any kind of I/O.)  More generally

foreach i in S:
    B[i] = f(i, x, y, ..)


is parallelizable if f is pure and does not access B (for reading or writing) and none of the arguments alias B.  However,

foreach i in S:
    B[i] = B[A[i]]


is not parallelizable, as there are dependencies between loop iterations.  (At least, it is not trivially parallelizable, if A is not known at compile time.)

I've written using foreach syntax but you can translate each example to map or apply and the same comments apply.