I have an environment variable for LANG set in ~/.profile but it is not getting set

There are many other initialization files where the variables may be set after applying your .profile such as .bash_profile .bashrc ...etc, or simply an other non standard file called from .profile itself. I suggest first you to look for every occurrences of your variables in your home directory :

grep "LANG=" .* 

In debian you set locales using the following command:

# dpkg-reconfigure locales

It will create the /etc/default/locale file and add only the LANG variable to it. If you want to customize all the LC_* variables, you can add them there as well:

LANG=en_US.UTF-8
LANGUAGE=
LC_CTYPE=en_US.UTF-8
LC_NUMERIC=en_US.UTF-8
LC_TIME=en_US.UTF-8
LC_COLLATE=C
LC_MONETARY=en_US.UTF-8
LC_MESSAGES=C
LC_PAPER=en_US.UTF-8
LC_NAME=en_US.UTF-8
LC_ADDRESS=en_US.UTF-8
LC_TELEPHONE=en_US.UTF-8
LC_MEASUREMENT=en_US.UTF-8
LC_IDENTIFICATION=en_US.UTF-8
LC_ALL=

Went through and figured this finally because it was driving me nuts having to do it manually, didn't seem right. On debian this can be done with the update-locale utility. The command

update-locale --reset

will cause the /etc/default/locale file to be ignored (it simply comments out the LANG variable); resulting in a locale of:

LANG=C
LANGUAGE=
LC_CTYPE="C"
LC_NUMERIC="C"
LC_TIME="C"
LC_COLLATE="C"
LC_MONETARY="C"
LC_MESSAGES="C"
LC_PAPER="C"
LC_NAME="C"
LC_ADDRESS="C"
LC_TELEPHONE="C"
LC_MEASUREMENT="C"
LC_IDENTIFICATION="C"
LC_ALL=C

The command

update-locale LANG=en_US.UTF-8

will set your LANG to... you guessed it en_US.UTF-8 resulting in locale generating:

LANG=en_US.UTF-8
LANGUAGE=
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=

And finally just to cover all my bases...

update-locale LANG=C

will set your LANG to C resulting in locale outputting:

LANG=C
LANGUAGE=
LC_CTYPE="C"
LC_NUMERIC="C"
LC_TIME="C"
LC_COLLATE="C"
LC_MONETARY="C"
LC_MESSAGES="C"
LC_PAPER="C"
LC_NAME="C"
LC_ADDRESS="C"
LC_TELEPHONE="C"
LC_MEASUREMENT="C"
LC_IDENTIFICATION="C"
LC_ALL=

Check if you have a ~/.bash_profile or ~/.bash_login; they will override ~/.profile.

From man bash:

When bash is invoked as an interactive login shell, or as a non-interactive shell with the --login option, it first reads and executes commands from the file /etc/profile, if that file exists. After reading that file, it looks for ~/.bash_profile, ~/.bash_login, and ~/.profile, in that order, and reads and executes commands from the first one that exists and is readable.

"As an interactive login shell" is significant, because interactive shells often are not login shells. If you just change one of those files and start a new GUI terminal, for example, it won't apply. It is only read when you actually log in.

Another possibility is that your LANG is being subsequently reset by the system wide bashrc; check to see if one is sourced in ~/.bashrc, then, e.g.

grep LANG /etc/bashrc