Thanks for the step by step description.

Following the explanations from "matrixise" 
I could also reproduce the bug when doing
":REcontroller te<TAB><TAB>"  which segfaults
(press tab twice):

  pel@pel-laptop:~/test_crash$ /usr/bin/vim   
  Vim: Caught deadly signal SEGV

This is happening with vim-full from Hardy:

  pel@pel-laptop:~/test_crash$ /usr/bin/vim --version 
  VIM - Vi IMproved 7.1 (2007 May 12, compiled Jan 31 2008 12:00:11)
  Included patches: 1-138

Now, running with valgrind, I can see several errors
but the last one must be the one which causes the
crash:

==10292== Invalid free() / delete / delete[]
==10292==    at 0x402265C: free (vg_replace_malloc.c:323)
==10292==    by 0x80CD2FA: ExpandOne (in /usr/bin/vim.gnome)
==10292==    by 0x80CF245: (within /usr/bin/vim.gnome)
==10292==    by 0x80D0EF3: getcmdline (in /usr/bin/vim.gnome)
==10292==    by 0x80C5AF3: do_cmdline (in /usr/bin/vim.gnome)
==10292==    by 0x81305FE: (within /usr/bin/vim.gnome)
==10292==    by 0x8132FAB: normal_cmd (in /usr/bin/vim.gnome)
==10292==    by 0x80F736F: main_loop (in /usr/bin/vim.gnome)
==10292==    by 0x80FA972: main (in /usr/bin/vim.gnome)
==10292==  Address 0x67f57b8 is 0 bytes inside a block of size 3 free'd
==10292==    at 0x402265C: free (vg_replace_malloc.c:323)
==10292==    by 0x80CD320: ExpandOne (in /usr/bin/vim.gnome)
==10292==    by 0x809744F: (within /usr/bin/vim.gnome)
==10292==    by 0x809D4D0: (within /usr/bin/vim.gnome)
==10292==    by 0x80A07F7: (within /usr/bin/vim.gnome)
==10292==    by 0x80A1D83: (within /usr/bin/vim.gnome)
==10292==    by 0x80A254C: (within /usr/bin/vim.gnome)
==10292==    by 0x809EF81: (within /usr/bin/vim.gnome)
==10292==    by 0x809F207: (within /usr/bin/vim.gnome)
==10292==    by 0x809FA3B: (within /usr/bin/vim.gnome)
==10292==    by 0x809FB5B: (within /usr/bin/vim.gnome)
==10292==    by 0x80A10CD: (within /usr/bin/vim.gnome)

Unfortunately, /usr/bin/vim is not built with symbols, but the
message shows that there is an invalid free() in the ExpandOne()
function of Vim.

If I download the latest vim (vim-7.1.293) source code (see
http://www.vim.org/download.php), and compiled it myself:

  cd vim7
  ./configure --with-features=huge
  make
  make install

Then it works fine and valgrind does not complain either.
So this bug must have already been already fixed in latest vim.

Note the Hardy is using vim-7.1.138 and latest vim from CVS
is vim-7.1.293.   It would be a good idea to do an Ubuntut
package with a more recent vim, many bugs have been fixed.
Here are all the missing patches in vim as shipped with 
Ubuntu:

  1557  7.1.139  fold truncated when ending Insert mode with CTRL-C
  1664  7.1.140  v:count can't be used in an expression mapping
  2806  7.1.141  GTK: can't use negative offset with -geom argument
  2161  7.1.142  ":redir @A>" doesn't work
  1723  7.1.143  uninitialized memory read when diffing three files
  1250  7.1.144  after ":diffup" cursor can be in the wrong position
  6160  7.1.145  stay in Insert completion mode depending on the char typed
  2838  7.1.146  VMS: writing fails for rare record organisation
  2079  7.1.147  (after 7.1.127) freeing memory twice completing user name
  2557  7.1.148  QNX and some other systems require testing for sys/types.h
  4823  7.1.149  completion menu messed up when using the scroll bar
  1759  7.1.150  Visual mode "p" doesn't work when 'clipboard' has "unnamed"
  2108  7.1.151  lalloc(0) error for line completion with 'ic' and 'inf' set
  3183  7.1.152  display problem when 'hls' and 'cursorcolumn' are set
  4610  7.1.153  compiler warnings on SGI
  1547  7.1.154  (after 7.1.152) compiler warning for signed/unsigned compare
  1594  7.1.155  crash when 'undolevels' is 0 and repeating "udd"
  4174  7.1.156  overlapping arguments for strcpy() during cmdline completion
  1541  7.1.157  :" in Ex mode at end of file results in an error message
  4629  7.1.158  (extra) Win32: with utf-8 and cp1250 Alt-y is the wrong char
  1646  7.1.159  overlapping arguments for a strcpy()
  1661  7.1.160  getting/losing focus may cause hit-enter prompt to be redrawn
  4347  7.1.161  compilation errors with tiny features and EXITFREE
  4691  7.1.162  crash when using a modifier before "while" or "for"
  2367  7.1.163  warning for the unknown option 'bufsecret'
  1576  7.1.164  reading past end of regexp pattern
  5538  7.1.165  crash related to getting X window ID
  2134  7.1.166  memory leak when using "gp" in Visual mode
  2528  7.1.167  xxd crashes when using "xxd -b -c 110"
  2989  7.1.168  (extra) Win32 GUI: when no focus click doesn't position cursor
  1926  7.1.169  using uninitialized memory when system() fails
  1722  7.1.170  overlapping arguments to strcpy()
  2324  7.1.171  reading one byte before allocated memory.
  1536  7.1.172  if 'buftype' is "acwrite" Vim still does overwrite check
  1928  7.1.173  accessing freed memory when using "\%^" pattern
  2197  7.1.174  writing NUL past end of a buffer
  4722  7.1.175  <BS> doesn't work with some combination of option settings
  2943  7.1.176  compiling with Aap fails if "compiledby" contains '<' or '>'
  5450  7.1.177  freeing memory twice when in debug mode while reading a script
  1567  7.1.178  "%" doesn't work on "/* comment *//* comment */"
  6581  7.1.179  configure doesn't find TCL 8.5
  7099  7.1.180  regexp patterns are not sufficiently tested
  1878  7.1.181  accessing uninitialized memory in Farsi mode with ":s"
  5457  7.1.182  with tab pages and an argument list session file may be wrong
  2489  7.1.183  Internal error for ":echo matchstr('a', 'a\%[\&]')"
  2132  7.1.184  crash when deleting backwards over a line break in Insert mode
  3744  7.1.185  "gR" and then BS doesn't work properly with multi-byte chars
  3294  7.1.186  "expand('<afile>')" returns a bogus value after ":cd dir"
  2341  7.1.187  Win32 GUI: custom completion using system() doesn't work
  1688  7.1.188  "W10" message could be displayed in the second column
  1950  7.1.189  (after 7.1.104) need to call plain_vgetc() in ask_yesno()
  1685  7.1.190  cursor after end-of-line: "iA sentence.<Esc>)"
  2007  7.1.191  Win32 GUI: when not in focus click in scrollbar doesn't work 
  2605  7.1.192  CTRL-C doesn't stop duplicating text for "s" in Visual block
  2962  7.1.193  some of the Vim 5.x digraphs could be supported
  1650  7.1.194  Unix: ":echo glob('~/{}')" results in "/home/user//"
  2273  7.1.195  '0 mark doesn't work for "~/foo ~ foo"
  2642  7.1.196  (extra) Win32 GUI: "\n" in a tooltip doesn't cause line break
  2308  7.1.197  Mac: "make install" doesn't work when $prefix is set
  1460  7.1.198  hang when using ":s/\n//gn"
  3572  7.1.199  can't do command line completion for a file name extension
  2310  7.1.200  (after 7.1.177 and 7.1.182) compiler warnings
  2705  7.1.201  when reading stdin 'fenc' and 'ff' are not set
  2383  7.1.202  incomplete utf-8 byte sequence is not checked for validity
  2261  7.1.203  if 'virtualedit' is "onemore" then ":normal 99|" is not right
  2891  7.1.204  (extra) Win32: 'balloonexpr' tooltip disappears after 4 sec
  5481  7.1.205  can't get the operator in an ":omap"
  1690  7.1.206  compiler warnings when using MODIFIED_BY
  7708  7.1.207  netbeans: "remove" cannot delete one line
  2051  7.1.208  on Alpha get an unaligned access error
  2249  7.1.209  GTK GUI: when using the netrw plugin ":gui" causes a hang
  1923  7.1.210  listing mapping for 0xdb fails when 'encoding' is utf-8
 25525  7.1.211  matchparen plugin may take so long it looks like Vim hangs
  1491  7.1.212  accessing a byte before a line
  1750  7.1.213  aborting ":tabedit" from the ATTENTION dialog leaves tab open
  8399  7.1.214  ":1s/g\n\zs1//" deletes characters from the first line
  6476  7.1.215  it's difficult to figure out the nesting of syntax items
  2360  7.1.216  variants of --remote-tab are not mentioned for "vim --help"
  7103  7.1.217  the "help-tags" tag may be missing from runtime/doc/tags
  1864  7.1.218  syntax region without "keepend" could be truncated
 12134  7.1.219  (after 7.1.215) synstack() doesn't work for one char region
  3928  7.1.220  cursor may end up on trail byte after ")"
  1978  7.1.221  when inserting a "(" the following highlighting may be wrong
  3531  7.1.222  (after 7.1.217) wildcards of ":helptags" are not expanded
  8138  7.1.223  glob() doesn't handle "'" when 'shell' is "sh" or "bash"
  2131  7.1.224  "vim -F -o one two" sets 'rightleft' in one window only
  1767  7.1.225  using unitialized value when XGetWMNormalHints() fails
  1957  7.1.226  command line completion fails for a file name with a '&' char
  5595  7.1.227  hang in syntax HL when moving over a ")"
  1678  7.1.228  with 'foldmethod' "indent" fold can't be closed after "3>>"
  1758  7.1.229  a fold is closed when backspacing in Insert mode
  2052  7.1.230  memory leak when executing SourceCmd autocommands
  8648  7.1.231  when shifting lines the change is acted upon multiple times
  2002  7.1.232  (after 7.1.207 and 7.1.211) compiler warnings with MSVC
  3249  7.1.233  crash with Insert mode completion for a user defined command
  6865  7.1.234  display problems when diff'ing three files
  5925  7.1.235  pattern matching is slow when using a lot of simple patterns
 28992  7.1.236  hang when using complicated pattern and 'hlsearch' or ":match"
  1704  7.1.237  compiler warning on an Alpha processor in Motif code
  1801  7.1.238  searchpair() may fail when using 'c' or 'r' flag
  1639  7.1.239  (after 7.1.233) compiler warning for sprintf() argument
  5157  7.1.240  "gUe" may stop before the end of the word
  3093  7.1.241  focus change events not always ignored
  2262  7.1.242  "cib" doesn't work properly on "(x)"
  4475  7.1.243  (after 7.1.240) "U" doesn't work on all text in Visual mode
  1847  7.1.244  GUI may have part of the command line cut off
  2767  7.1.245  pressing CTRL-\ three times causes Vim to quit
  2739  7.1.246  configure hangs when the man pager is something strange
  6028  7.1.247  Netbeans: backspacing in Insert mode may skip a character
  3691  7.1.248  can't set the '" mark; can't know if setpos() was successful
  2144  7.1.249  after "U" the cursor can be past end of line
  1684  7.1.250  error for ":setglobal fenc=anything" when 'modifiable' is off
  3134  7.1.251  accessing freed memory when spell checking enabled
  1399  7.1.252  (after 7.1.243) test 39 fails when locale uses utf-8 encoding
  1751  7.1.253  ":sort" doesn't work in a one line file
  1894  7.1.254  Tests 49 and 55 fail when the locale is French
  1514  7.1.255  Vim doesn't support utf-32
 50921  7.1.256  findfile() also returns directories
  3326  7.1.257  configure can't always find the Tcl header files
  3360  7.1.258  crash when doing "d/\n/e" and 'virtualedit' is "all"
  1944  7.1.259  cursor in wrong place with 'rl', "utf-8" and illegal byte
  1805  7.1.260  cursor position wrong after ^@ wrapping halfway if using utf-8
  2255  7.1.261  for a 2 byte BOM UCS-2 is used, which doesn't work for UTF-16
  3438  7.1.262  can't get the process ID of Vim
  2442  7.1.263  filetype with dot doesn't work for indent plugins
  6295  7.1.264  crash when C-indenting
  1310  7.1.265  hang when completing file name and space in 'isfname'
  2510  7.1.266  version string returned by terminal may be used as typed input
  1957  7.1.267  when changing folds cursor may be positioned in a wrong place
  1576  7.1.268  always shows "+" at end of screen line with 'cursurline'
  6183  7.1.269  matchparen plugin has an arbitrary line number limit
  2861  7.1.270  ":?foo?" matches in current line since patch 7.1.025
  1582  7.1.271  in tiny version ":!touch %" causes curbuf to be wrong
  2334  7.1.272  buffer name [Location List] not used for buffer in other tab
  2504  7.1.273  when profiling on Linux Vim exits early
  1549  7.1.274  (after 7.1.272) compiler warning with optimized build
 40835  7.1.275  (extra) Mac: ATSUI and 'antialias' don't work together
  4946  7.1.276  "gw" uses 'formatexpr', even though the docs say it doesn't
  2802  7.1.277  default for 'paragraphs' misses some items
  1989  7.1.278  (extra, after 7.1.275) build problem
  3848  7.1.279  when using cscope temporary files are left behind
  1556  7.1.280  (after 7.1.275) Mac: build problems without multibyte feature
  2094  7.1.281  (after 7.1.279) Vim hangs when cscope doesn't exit
 16302  7.1.282  (extra) Win64: Installing context menu, compiler warnings
  7633  7.1.283  non-extra part of 7.1.282
  2258  7.1.284  compiler warnings for functions without prototype
  5787  7.1.285  (extra) Mac: dialog hotkeys don't work
  2045  7.1.286  (after 7.1.103) "w" at end of buffer moves cursor too far
  1859  7.1.287  crash when reversing a list after using it
  3182  7.1.288  (after 7.1.281) cscope leaves behind temp files with gvim
  1979  7.1.289  when EXITFREE is defined and 'acd' is set freed memory is used
  2146  7.1.290  reading unwritten bytes when spell checking with large indent
  1940  7.1.291  compiler warning for int-long conversion
  6698  7.1.292  when using a pattern with "\@<=" the submatches can be wrong
  3087  7.1.293  spell checking considers super/subscript chars as word chars


Note that several crash bug have been fixed from vim-7.1.138 to vim-7.1.293.

I do hope that Ubuntu developers will create a vim package with 
a more recent vim.

In the mean time, it's probably best to compile vim yourself.