What is the difference between "used to" and "I was used to"?

What is the difference in the meaning between the following two tenses?

I used to travel alone.
I was used to traveling alone.

"I used to [do X]" indicates an activity that you have previously performed regularly, but no longer do.

"I was used to [doing X]" indicates that you were accustomed to engaging in a particular activity.

Some examples:

I used to travel alone, but now I always take my whole family with me.

I was used to traveling alone, so having my whole family along has been a big adjustment for me to make.

Used to describes an action or state of affairs that was done repeatedly or existed for a period in the past; to be used to (or to get used to) means "be or become familiar with someone or something through experience".

I used to go in southern Italy every summer.
I was used to understand when somebody was lying.

Both the phrases imply that an action has been done repeatedly; they are not used to refer to actions that happened only once.

? I used to go in souther Italy once in all my life.

The NOAD reports the following notes about used to that could interest you.

The construction used to is standard, but difficulties arise with the formation of negatives and questions. Traditionally, used to behaves as a modal verb, so that questions and negatives are formed without the auxiliary verb do, as in:
- It used not to be like that.
- Used she to come here?
In modern English, this question form is now regarded as very formal or old-fashioned and the use with do is broadly accepted as standard, as in:
- Did she use to come here?
Negative constructions with do, on the other hand (as in it didn't use to be like that), although common, are informal and are not generally accepted.

There is sometimes confusion over whether to use the form used to or use to, which has arisen largely because the pronunciation is the same in both cases. Except in negatives and questions, the correct form is used to: we used to go to the movies all the time (not we use to go to the movies). However, in negatives and questions using the auxiliary verb do, the correct form is use to, because the form of the verb required is the infinitive: I didn't use to like mushrooms (not I didn't used to like mushrooms).

The sequence of words used to can occur in many kinds of sentence; in a passive sentence, for instance

• A shovel is used to dig holes with.
  (note that this occurrence of used to is pronounced with a /z/: /'yuztə/)

the sequence used to is not a constituent, just two words stuck together.

The discussion in this item, and in all the other questions this is discussed in -- again and again -- gets confused because people are thinking of idioms as being sequences of words, and they're not distinguishing sequences of words with two different idioms with completely different meanings and completely different grammars. They are, in effect, completely different words.

Two very common idioms in English include the sequence used to, both of which are pronounced with an /s/, never a /z/: /'yustə/. This pronunciation is part of the two idioms, and distinguishes the idioms from the simple sequence of words:

• the past continuous generic or imperfect construction [used to + Infinitive],
  (the next verb, describing the past, must be an infinitive form, not a gerund), as in
  • We used to live there before my parents got divorced.
  • I used to feel strongly about that, but I don't any more.

and

• [be used to + NP], the idiomatic predicate adjective synonym of be accustomed (to),
  (which requires both auxiliary be verb and preposition to with object noun phrase), as in
  • She was used to daily meetings.
  • He was used to taking notes at meetings.
    (the NP that's the object of to can be a gerund complement clause, but not an infinitive)

So there are three things to distinguish:

1. a sequence of used and to. Not an idiom. Pronounced with /z/.

2. a past continuous verb idiom; requires to infinitive complement. Pronounced with /s/

3. an idiomatic predicate adjective; allows gerund complement. Pronounced with /s/.

Only sequence (1) has to do with the meaning of use or the meaning of to. Idioms (2) and (3) are not related to one another, nor even to the words they're made of. Idioms are those constructions whose meaning is not constructible from the meanings of its constituent parts.