Issue 1:
Got another ICE, this time it only shows itself when compiled with debug info (rustc -g error.rs).

Also of note is that another ICE shows itself if the State wrapper is removed (I can file a separate report for that if you want but I figure they might be the same issue).

struct State<I>;

trait Parser {
type Input;
}

impl Parser for () {
type Input = ();
}

struct IntoIter<P: Parser> {
input: State<<P as Parser>::Input>
}

fn main() {
let p = IntoIter::<()> { input: State::<()> };
}
//Compile with rustc error.rs -g

error: internal compiler error: get_unique_type_id_of_type() - unexpected type:
<() as Parser>::Input, ty_projection(ProjectionTy { trait_ref: Rc(TraitRef { def_id: DefId { krate: 0u32, node: 8u32 }, substs: Substs { types: VecPerParamSpace {TypeSpace: [], SelfSpace: [TyS { sty: ty_tup([]), flags: 0, region_depth: 0u32 }], FnSpace: [], }, regions: NonerasedRegions(VecPerParamSpace {TypeSpace: [],
SelfSpace: [], FnSpace: [], }) } }), item_name: "Input"(64) })
note: the compiler unexpectedly panicked. this is a bug.
note: we would appreciate a bug report: http://doc.rust-lang.org/complement-bugreport.html
note: run with `RUST_BACKTRACE=1` for a backtrace
thread 'rustc' panicked at 'Box<Any>', C:\bot\slave\nightly-dist-rustc-win-64\build\src\libsyntax\diagnostic.rs:182

stack backtrace:
1: 0x69bec997 - sys::backtrace::write::h62d87c63e18a3ea5JRt
2: 0x69c00672 - rt::unwind::register::haa3a38fa07bfa9beVGz
3: 0x69b834a7 - rt::unwind::begin_unwind_inner::hbebf9f8c0125ffc9tEz
4: 0x6f898116 - diagnostic::SpanHandler::span_bug::hebc2106d060dd9d6xSF
5: 0x6f8989c5 - diagnostic::Handler::bug::hd75d92a08fdf3c17DYF
6: 0x801852 - session::Session::bug::h9385caa3fe1c8dc3wQq
7: 0x11467b7 - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
8: 0x114a57a - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
9: 0x1147448 - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
10: 0x114c721 - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
11: 0x1154a87 - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
12: 0x11545ca - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
13: 0x11504ef - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
14: 0x11531f4 - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
15: 0x114d472 - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
16: 0x114eaa2 - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
17: 0x114e2bf - trans::debuginfo::UniqueTypeId...std..fmt..Show::fmt::h6619b90c5d2210b6NBD
18: 0x1033554 - trans::cleanup::FunctionContext<'blk, 'tcx>.CleanupMethods<'blk, 'tcx>::pop_and_trans_ast_cleanup_scope::h80e56e364b2716daMFK
19: 0x10fd20a - trans::base::IsUnboxedClosureFlag...std..clone..Clone::clone::h7d2a86d65666b43aQYt
20: 0x101e571 - trans::context::CrateContext<'b, 'tcx>::sess::h6fdd1e7dea5490cdItm
21: 0x1019cc3 - trans::context::CrateContext<'b, 'tcx>::stats::hd7a1dc7a2465d605EGm
22: 0x1103768 - trans::base::trans_crate::h4bc502f506e6c118Wsv
23: 0x70b2af6a - driver::phase_4_translate_to_llvm::haa9c5e826483e242PFa
24: 0x70b03623 - driver::compile_input::hf5b2f58693da03b5xba
25: 0x70bd1eec - run::ha65e56249318cc0dV3b
26: 0x70bd04cc - run::ha65e56249318cc0dV3b
27: 0x70bcf16a - run::ha65e56249318cc0dV3b
28: 0x69c2881c - rust_try
29: 0x69c287f9 - rust_try
30: 0x70bcf854 - run::ha65e56249318cc0dV3b
31: 0x69bf14a7 - sys::tcp::TcpListener::bind::hc4a8da4adad0f541bsw
32: 0x7fff4c8816ad - BaseThreadInitThunk

rustc 1.0.0-nightly (44a287e6e 2015-01-08 17:03:40 -0800)
binary: rustc
commit-hash: 44a287e6eb22ec3c2a687fc156813577464017f7
commit-date: 2015-01-08 17:03:40 -0800
host: x86_64-pc-windows-gnu
release: 1.0.0-nightly

Issue 2:
I thought that my example in #20368 was sufficient to cover one of my desired uses of associated types, but, while that example does now successfully compile, the module I really wanted to improve still fails with yet another ICE. Here's the module in full:

use std::default::Default;
use std::io::IoResult;
use std::io::fs;
use std::io::fs::PathExtensions;

/// A strategy for acquiring more subpaths to walk.
pub trait Strategy {
type P: PathExtensions;
/// Get additional subpaths from a given path.
fn get_more(&self, item: &Self::P) -> IoResult<Vec<Self::P>>;
/// Determine whether a path should be walked further.
/// This is run against each item from `get_more()`.
fn prune(&self, p: &Self::P) -> bool;
}

/// The basic fully-recursive strategy. Nothing is pruned.
#[derive(Copy, Default)]
pub struct Recursive;

impl Strategy for Recursive {
type P = Path;
fn get_more(&self, p: &Path) -> IoResult<Vec<Path>> { fs::readdir(p) }

fn prune(&self, _: &Path) -> bool { false }
}

/// A directory walker of `P` using strategy `S`.
pub struct Subpaths<S: Strategy> {
stack: Vec<S::P>,
strategy: S,
}

impl<S: Strategy> Subpaths<S> {
/// Create a directory walker with a root path and strategy.
pub fn new(p: &S::P, strategy: S) -> IoResult<Subpaths<S>> {
let stack = try!(strategy.get_more(p));
Ok(Subpaths { stack: stack, strategy: strategy })
}
}

impl<S: Default + Strategy> Subpaths<S> {
/// Create a directory walker with a root path and a default strategy.
pub fn walk(p: &S::P) -> IoResult<Subpaths<S>> {
Subpaths::new(p, Default::default())
}
}

impl<S: Default + Strategy> Default for Subpaths<S> {
fn default() -> Subpaths<S> {
Subpaths { stack: Vec::new(), strategy: Default::default() }
}
}

impl<S: Strategy> Iterator for Subpaths<S> {
type Item = S::P;
fn next (&mut self) -> Option<S::P> {
let mut opt_path = self.stack.pop();
while opt_path.is_some() && self.strategy.prune(opt_path.as_ref().unwrap()) {
opt_path = self.stack.pop();
}
match opt_path {
Some(path) => {
if PathExtensions::is_dir(&path) {
let result = self.strategy.get_more(&path);
match result {
Ok(dirs) => { self.stack.extend(dirs.into_iter()); },
Err(..) => { }
}
}
Some(path)
}
None => None,
}
}
}

#[test]
fn woot() {
let mut walker: Subpaths<Recursive> = Subpaths::walk(&Path::new("/home")).unwrap();
}

Here's the error and backtrace:

error: internal compiler error: get_unique_type_id_of_type() - unexpected type: <Recursive as Strategy>::P, ty_projection(ProjectionTy { trait_ref: Rc(TraitRef { def_id: DefId { krate: 0u32, node: 8u32 }, substs: Substs { types: VecPerParamSpace {TypeSpace: [], SelfSpace: [TyS { sty: ty_struct(DefId { krate: 0u32, node: 40u32 }, Substs { types: VecPerParamSpace {TypeSpace: [], SelfSpace: [], FnSpace: [], }, regions: ErasedRegions }), flags: 0, region_depth: 0u32 }], FnSpace: [], }, regions: NonerasedRegions(VecPerParamSpace {TypeSpace: [], SelfSpace: [], FnSpace: [], }) } }), item_name: "P"(73) })
note: the compiler unexpectedly panicked. this is a bug.
note: we would appreciate a bug report: http://doc.rust-lang.org/complement-bugreport.html
note: run with `RUST_BACKTRACE=1` for a backtrace
thread 'rustc' panicked at 'Box<Any>', /home/samuel/rust/src/libsyntax/diagnostic.rs:182

stack backtrace:
1: 0x7f4a265a0570 - sys::backtrace::write::h3452feb04e320bcfCzt
2: 0x7f4a265c2780 - failure::on_fail::hd0efae8686875716aPz
3: 0x7f4a26530300 - rt::unwind::begin_unwind_inner::h229232f5734654792tz
4: 0x7f4a214ada20 - rt::unwind::begin_unwind::h9438643137198476843
5: 0x7f4a214ae2d0 - diagnostic::Handler::bug::he657a4296d705a33tWF
6: 0x7f4a2488f180 - session::Session::bug::ha8836431c543757ciRq
7: 0x7f4a25673ba0 - trans::debuginfo::TypeMap<'tcx>::get_unique_type_id_of_type::h606c89215412cd5brGD
8: 0x7f4a256778d0 - trans::debuginfo::TypeMap<'tcx>::get_unique_type_id_of_type::from_def_id_and_substs::h9fa1f90635ed12d03PD
9: 0x7f4a25673ba0 - trans::debuginfo::TypeMap<'tcx>::get_unique_type_id_of_type::h606c89215412cd5brGD
10: 0x7f4a25679e30 - trans::debuginfo::type_metadata::h7557684678d0dd25RSF
11: 0x7f4a25682220 - trans::debuginfo::StructMemberDescriptionFactory<'tcx>::create_member_descriptions::unboxed_closure.45598
12: 0x7f4a25681e00 - vec::Vec<T>.FromIterator<T>::from_iter::h9648212210143919248
13: 0x7f4a2567dda0 - trans::debuginfo::StructMemberDescriptionFactory<'tcx>::create_member_descriptions::hf79fdc4d3167c5d0j9E
14: 0x7f4a25680980 - trans::debuginfo::RecursiveTypeDescription<'tcx>::finalize::h0ff9cf1ab1bdbcef26E
15: 0x7f4a25679e30 - trans::debuginfo::type_metadata::h7557684678d0dd25RSF
16: 0x7f4a25684fd0 - trans::debuginfo::VariantMemberDescriptionFactory<'tcx>::create_member_descriptions::unboxed_closure.45632
17: 0x7f4a25684be0 - vec::Vec<T>.FromIterator<T>::from_iter::h5453357870208096995
18: 0x7f4a25683270 - trans::debuginfo::EnumMemberDescriptionFactory<'tcx>::create_member_descriptions::unboxed_closure.45606
19: 0x7f4a25682e50 - vec::Vec<T>.FromIterator<T>::from_iter::h13188062602912948975
20: 0x7f4a2567de90 - trans::debuginfo::EnumMemberDescriptionFactory<'tcx>::create_member_descriptions::h1355d0387a727939hgF
21: 0x7f4a25680980 - trans::debuginfo::RecursiveTypeDescription<'tcx>::finalize::h0ff9cf1ab1bdbcef26E
22: 0x7f4a25679e30 - trans::debuginfo::type_metadata::h7557684678d0dd25RSF
23: 0x7f4a25688070 - trans::debuginfo::subroutine_type_metadata::haec4c13f9a5d7a59vOF
24: 0x7f4a25679e30 - trans::debuginfo::type_metadata::h7557684678d0dd25RSF
25: 0x7f4a25620ae0 - trans::debuginfo::create_function_debug_context::h985b11ad61da52fdwsE
26: 0x7f4a25580890 - trans::base::new_fn_ctxt::hbe79965b1049ecf2Zxt
27: 0x7f4a25626410 - trans::base::trans_closure::h5c0a7253f08a6c1bEYt
28: 0x7f4a255452b0 - trans::base::trans_fn::h84cc11dd50b05f50j9t
29: 0x7f4a25545710 - trans::monomorphize::monomorphic_fn::h44708ba9400c75dbFpd
30: 0x7f4a25597ff0 - trans::callee::trans_fn_ref_with_substs::h1741ea29b53c270fGxg
31: 0x7f4a25596590 - trans::callee::trans_fn_ref::h611f01f0cbdf2e42Rlg
32: 0x7f4a25593870 - trans::callee::trans::h2d6fbfb713fd152ayag
33: 0x7f4a2559da90 - trans::callee::trans_call_inner::h893956557312987459
34: 0x7f4a255a34b0 - trans::expr::trans_rvalue_dps_unadjusted::h4ab35d4af002299e1Si
35: 0x7f4a255a2790 - trans::expr::trans_unadjusted::h15f19eba475549d3Oji
36: 0x7f4a2555b000 - trans::expr::trans::ha962b869e642f0b8eCh
37: 0x7f4a2556c0b0 - trans::callee::trans_args::h2dbfd3d1c7128174xch
38: 0x7f4a2559f460 - trans::callee::trans_call_inner::h11730372111330536098
39: 0x7f4a255a34b0 - trans::expr::trans_rvalue_dps_unadjusted::h4ab35d4af002299e1Si
40: 0x7f4a25559d90 - trans::expr::trans_into::h70023b40e1df277dKyh
41: 0x7f4a2565e030 - trans::_match::mk_binding_alloca::h14708251032129145358
42: 0x7f4a25559390 - trans::base::init_local::h17113ff3a822f41bC7s
43: 0x7f4a2555a3e0 - trans::controlflow::trans_block::hd4046f45161d1f00B3d
44: 0x7f4a25626410 - trans::base::trans_closure::h5c0a7253f08a6c1bEYt
45: 0x7f4a255452b0 - trans::base::trans_fn::h84cc11dd50b05f50j9t
46: 0x7f4a25540840 - trans::base::trans_item::h560b1558a6cec5e6Ewu
47: 0x7f4a2562dc30 - trans::base::trans_crate::heb94c899d24982b8lsv
48: 0x7f4a26b09fa0 - driver::phase_4_translate_to_llvm::h4be77ff61772864dPFa
49: 0x7f4a26ae3f30 - driver::compile_input::hefa96b3bea08e00bxba
50: 0x7f4a26bb3bc0 - monitor::unboxed_closure.22498
51: 0x7f4a26bb3a20 - thunk::F.Invoke<A, R>::invoke::h2604081160332846052
52: 0x7f4a26bb27a0 - rt::unwind::try::try_fn::h10712615664574212328
53: 0x7f4a26630f00 - rust_try_inner
54: 0x7f4a26630ef0 - rust_try
55: 0x7f4a26bb2a90 - thunk::F.Invoke<A, R>::invoke::h6088602545528080049
56: 0x7f4a265b0630 - sys::thread::thread_start::h803dac673dcdb1abqrw
57: 0x7f4a20cc7250 - start_thread
58: 0x7f4a261e0219 - clone
59: 0x0 - <unknown>

Could not compile `subpaths`.